Prolog - begin traversal at the end of a list?

Author

begin traversal at the end of a list?

meratech@gmail.com

2007-03-28, 7:08 pm

I was wondering if it was possible to begin traversal at the end of a
list without first using reverse to reverse the list and then doing
the traversal. If applying reverse to the list is the only way to
technically begin traversal at the end of the list, then let me know.
Thanks.

Duncan Patton

2007-03-28, 7:08 pm

On 28 Mar 2007 06:23:19 -0700
meratech@gmail.com wrote:

> I was wondering if it was possible to begin traversal at the end of a
> list without first using reverse to reverse the list and then doing
> the traversal. If applying reverse to the list is the only way to
> technically begin traversal at the end of the list, then let me know.
> Thanks.
>

If I get what you are asking this is the case because prolog lists are
recursive structures that consist of a "Head" and "Tail", with the tail
pointing to another Head and Tail. Composition of a proper list always
begins by declaring that it contains something and the empty set [], so
the only way to access the last element is to step thru the pointers
thru to the end. Lists are not random access like arrays, they are
sequential access data items.

If, for some reason, you need to process something from the ends in,
reverse the list to rlist and process both list and rlist until they
hit the middle.

Dhu

Peter Van Weert

2007-03-28, 7:08 pm

meratech@gmail.com schreef:
> I was wondering if it was possible to begin traversal at the end of a
> list without first using reverse to reverse the list and then doing
> the traversal. If applying reverse to the list is the only way to
> technically begin traversal at the end of the list, then let me know.
> Thanks.
>

Not sure you provided enough information, but here are the basic idioms:

% Processing of the elements of a list from left to right:
traverse_l2r([]).
traverse_l2r([X|Xs]) :- process(X), traverse_l2r(Xs).

% Processing them from right to left:
traverse_r2l([]).
traverse_r2l([X|Xs]) :- traverse_r2l(Xs), process(X).

% for example:
process(X) :- writeln(X).

Cheers,
Peter

meratech@gmail.com

2007-03-28, 7:08 pm

Hey,

Sorry if I wasn't clear enough. What I meant is, suppose I have this
list [1,2,3] and instead of traversing it 1,2,3, I want to traverse it
3,2,1 because I will be comparing some elements with them. I thought
that the only way to do it would be to reverse [1,2,3] first and then
traverse it. However, it doesn't seem that way. Thanks Peter.

A.L.

2007-03-28, 7:08 pm

On 28 Mar 2007 10:38:17 -0700, meratech@gmail.com wrote:

>Hey,
>
>Sorry if I wasn't clear enough. What I meant is, suppose I have this
>list [1,2,3] and instead of traversing it 1,2,3, I want to traverse it
>3,2,1 because I will be comparing some elements with them. I thought
>that the only way to do it would be to reverse [1,2,3] first and then
>traverse it. However, it doesn't seem that way. Thanks Peter.

I am afraid that either you don't know what you want, or you just
ignored previous post.

The following code

traverse_r2l([]).
traverse_r2l([X|Xs]) :- traverse_r2l(Xs), write(X).

gives the following result

| ?- traverse_r2l([1,2,3]).
321
yes
| ?-

If this is not this what you want, then what you want?...

A.L.

meratech@gmail.com

2007-03-28, 7:08 pm

On Mar 28, 2:36 pm, A.L. <f...@2005.com> wrote:
> On 28 Mar 2007 10:38:17 -0700, merat...@gmail.com wrote:
>
>
>
> I am afraid that either you don't know what you want, or you just
> ignored previous post.
>
> The following code
>
> traverse_r2l([]).
> traverse_r2l([X|Xs]) :- traverse_r2l(Xs), write(X).
>
> gives the following result
>
> | ?- traverse_r2l([1,2,3]).
> 321
> yes
> | ?-
>
> If this is not this what you want, then what you want?...
>
> A.L.

That's what I wanted and I said Thanks to Peter in the end of the
message.

A.L.

2007-03-28, 7:08 pm

X-Newsreader: Forte Agent 4.2/32.1117
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Complaints-To: abuse@supernews.com
Lines: 10
Xref: number1.nntp.dca.giganews.com comp.lang.prolog:31949

On 28 Mar 2007 11:54:00 -0700, meratech@gmail.com wrote:

>
>That's what I wanted and I said Thanks to Peter in the end of the
>message.

Ok... I didn't notice double negation :)

A.L.

meratech@gmail.com

2007-03-28, 7:08 pm

Yeah, my response was worded poorly. I apologize. But the problem has
been addressed. Thanks for the help.

student

2007-03-29, 4:19 am

meratech@gmail.com wrote:
> Hey,
>
> Sorry if I wasn't clear enough. What I meant is, suppose I have this
> list [1,2,3] and instead of traversing it 1,2,3, I want to traverse it
> 3,2,1 because I will be comparing some elements with them. I thought
> that the only way to do it would be to reverse [1,2,3] first and then
> traverse it. However, it doesn't seem that way. Thanks Peter.
>

Another way that might be applicable depending on what you have in
mind to do would be by using "right-handed" list structures like

d(d(d(d(nil, 4), 3), 2), 1)

so that, for example, if

traverse_rlist(nil).
traverse_rlist(d(RL,X)) :-
write(X),nl,
traverse_rlist(RL).

then a query such as

RL=d(d(d(d(nil, 4), 3), 2), 1),traverse_rlist(RL).

gives

1
2
3
4

RL = d(d(d(d(nil, 4), 3), 2), 1) ;
No.

To convert to/from lists from/to rlists,

list_rlist([],nil).
list_rlist([X|L],d(RL,X)) :-
list_rlist(L,RL).

Interesting idea to play around with if nothing else. :)

student

2007-04-24, 7:04 pm

student wrote:
> meratech@gmail.com wrote:
>
> Another way that might be applicable depending on what you have in mind
> to do would be by using "right-handed" list structures like
>
> d(d(d(d(nil, 4), 3), 2), 1)
>
> so that, for example, if
>
> traverse_rlist(nil).
> traverse_rlist(d(RL,X)) :-
> write(X),nl,
> traverse_rlist(RL).
>
> then a query such as
>
> RL=d(d(d(d(nil, 4), 3), 2), 1),traverse_rlist(RL).
>
> gives
>
> 1
> 2
> 3
> 4
>
> RL = d(d(d(d(nil, 4), 3), 2), 1) ;
> No.
>
> To convert to/from lists from/to rlists,
>
> list_rlist([],nil).
> list_rlist([X|L],d(RL,X)) :-
> list_rlist(L,RL).
>
> Interesting idea to play around with if nothing else. :)

I apologize for posting the above. It may be an interesting idea to
play around with, but it is not relevant to the question being asked.

My 'rlists' and Prolog's predefined 'lists' are both "stacks", i.e.,
"last in, first out" (LIFO) queues, and a right-ended d(L,X) stack is
obviously no more help than a left-ended [X|L] stack if what is called
for is a way to represent a "first in, first out" (FIFO) queue.

As other responses in this thread have pointed out, it is possible
(by effectively using the call stack implicit in the P.I.E. to reverse
the given list) to /process/ the members of a Prolog list in FIFO order,
but the definition of Prolog does not at this time seem to me to provide
a way to /represent/ a FIFO queue in Prolog in the way that

[X|L]

represents a list in Prolog.

To represent a volatile ordered sequential structure in Prolog in a
way that allow /its representation/ to be accessed from either end would
seem to me to require some new Prolog /terms/, along the lines
(recalling Backus' 1977 ACM Award Turing Lecture "Can Programming Be
Liberated from the von Neumann Style? A Functional Style and its Algebra
of Programs")

:- < X ] RQ > = <1, 2, 3>.
X = 1,
RQ = <2, 3>

:- < LQ [ Y > = <1, 2, 3>.
LQ = <1, 2>,
Y = 3

:- < X ] Q [ Y > = <1, 2, 3>.
X = 1,
Q = <2>,
Y = 3

and perhaps a few other related changes.

One could then define predicates such as

lmember( X, < X ] _ > ).
lmember( X, < _ ] RQ > ) :- lmember(X, RQ).

rmember( < _ [ Y >, Y ).
rmember( < LQ [ _ >, Y ) :- rmember(LQ, Y).

billh

Joachim Schimpf

2007-04-25, 7:03 pm

student wrote:
> student wrote:
>
> My 'rlists' and Prolog's predefined 'lists' are both "stacks", i.e.,
> "last in, first out" (LIFO) queues, and a right-ended d(L,X) stack is
> obviously no more help than a left-ended [X|L] stack if what is called
> for is a way to represent a "first in, first out" (FIFO) queue.

Exactly. Swapping the argument order of your cons-functor doesn't
buy you anything for programming, it only makes for a different
printed representation, and it breaks some nice properties like the
one that standard term order on lists corresponds to lexicographic
order (e.g. [1,2,3] @< [1,3,1]).

>
> ...
>
> To represent a volatile ordered sequential structure in Prolog in a
> way that allow /its representation/ to be accessed from either end would
> seem to me to require some new Prolog /terms/,
> ...

If you care mainly about accessing elements, and not too much about
efficiently inserting/removing, you can just use a redundant data
structure that contains both a forward and a backward list of the
same elements. Then access to first and last are constant time,
reversing is constant time(!), but adding and removing is linear:

list_deque(Ls, Ls-Rs) :-
reverse(Ls, Rs).

leftmost([X|_]-_, X).

rightmost(_-[X|_], X).

lmember(X, Ls-_) :- member(X, Ls).

rmember(X, _-Rs) :- member(X, Rs).

ladd(X, Ls-Rs, [X|Ls]-RsX) :- % add/remove left
append(Rs, [X], RsX).

radd(X, Ls-Rs, LsX-[X|Rs]) :- % add/remove right
append(Ls, [X], LsX).

deque_reverse(Ls-Rs, Rs-Ls).

?- list_deque([1, 2, 3], Deque), rmember(X, Deque).
Deque = [1, 2, 3] - [3, 2, 1]
X = 3
Yes (0.00s cpu, solution 1, maybe more)
Deque = [1, 2, 3] - [3, 2, 1]
X = 2
Yes (0.00s cpu, solution 2, maybe more)
Deque = [1, 2, 3] - [3, 2, 1]
X = 1
Yes (0.00s cpu, solution 3)

-- Joachim

student

2007-04-25, 7:03 pm

student wrote:
> student wrote:
[..[
> To represent a volatile ordered sequential structure in Prolog in a
> way that allow /its representation/ to be accessed from either end would
> seem to me to require some new Prolog /terms/, along the lines
> (recalling Backus' 1977 ACM Award Turing Lecture "Can Programming Be
> Liberated from the von Neumann Style? A Functional Style and its Algebra
> of Programs")
>
> :- < X ] RQ > = <1, 2, 3>.
> X = 1,
> RQ = <2, 3>
>
> :- < LQ [ Y > = <1, 2, 3>.
> LQ = <1, 2>,
> Y = 3
>
> :- < X ] Q [ Y > = <1, 2, 3>.
> X = 1,
> Q = <2>,
> Y = 3
>
> and perhaps a few other related changes.
>
> One could then define predicates such as
>
> lmember( X, < X ] _ > ).
> lmember( X, < _ ] RQ > ) :- lmember(X, RQ).
>
> rmember( < _ [ Y >, Y ).
> rmember( < LQ [ _ >, Y ) :- rmember(LQ, Y).
>
>

Another example:

/*

Bell's Triangle

1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 ...

[http://mathworld.wolfram.com/BellTriangle.html]

% ---- Definition:

Let

bell_row(0) = <>

bell_row(n) = <b(1),...,b(n-1), b(n)>, n > 0.

Then

bell_row(n+1) = <c(1), ..., c(n+1)>,

where

c(1) = b(n)

c(k) = b(k) + c(k-1) for k=2, ..., n

and

c(n+1) = b(n) + c(n).

% ---- Implementation:

/*
bell_row(*$integer, *$integer)
------------------------------
input: <b(1),...,b(n-1),b(n)>
ouput: <<c(1),...,c(n-1),c(n)>[c(n+1)>
*/
bell_row(<>,<1> ).
bell_row(<Bs_1_to_n_minus_1[B_n>, <Cs_1_to_n[C_n_plus_1> ) :-
C_1 = B_n,
combine(<Bs_1_to_n_n_minus_1[B_n>, C_1, Cs_1_to_n),
<_[C_n> = Cs_1_to_n,
C_n_plus_1 is B_n + C_n.

/*
combine(*$integer, $integer, $integer)
--------------------------------------
input: <b(1),...,b(n-1),b(n)>, c(1)
output: <c(1),...,c(n-1),c(n)>
*/
combine(<>, _, <> ).
combine(<B_1]Bs_2_to_n>, C_1, <C_1]Cs_2_to_n> ) :-
C_2 is B_1 + C_1,
combine(Bs_2_to_n, C_2, Cs_2_to_n).

*/

bell_row([], [1]).
bell_row([B1|Bs_2_to_n], Cs_1_to_n_plus_1) :-
get_last([B1|Bs_2_to_n], B_n),
C_1 = B_n,
combine([B1|Bs_2_to_n], C_1, Cs_1_to_n),
get_last(Cs_1_to_n, C_n),
C_n_plus_1 is B_n + C_n,
put_last(C_n_plus_1, Cs_1_to_n, Cs_1_to_n_plus_1).

get_last([X], X).
get_last([_,X|L], Y) :-
get_last([X|L], Y).

put_last(X, [], [X]).
put_last(X, [Y|L1], [Y|L2]) :-
put_last(X, L1, L2).

combine([], _, []).
combine([B_1|Bs_2_to_n], C_1, [C_1|Cs_2_to_n]) :-
C_2 is B_1 + C_1,
combine(Bs_2_to_n, C_2, Cs_2_to_n).

/*
% -- Note: if we stipulated that

<> = []

% -- and

<X> = [X],

% -- then
*/

run :-
bell_triangle([]).

% -- and

bell_triangle(Bs) :-
bell_row(Bs, NewBs),
write(NewBs),
get_single_char(Response),
more([Response]),nl,
!,
bell_triangle(NewBs).
bell_triangle(_) :-
write('ok'),nl.

% -- and

more([13]).

% -- would work the same in both versions.

billh

Markus Triska

2007-04-25, 10:03 pm

student <nospam@nowhere.net> writes:

> write(NewBs),
> get_single_char(Response),
> more([Response]),nl,
> !,
> bell_triangle(NewBs).

By introducing an additional argument that is used to report solutions
incrementally, this kind of querying can be delegated to the toplevel:

aitken(R, R).
aitken(R0, R) :-
last(R0, L),
row(R0, L, R1),
aitken([L|R1], R).

row([], _, []).
row([A|As], B, [C|Cs]) :-
C is A + B,
row(As, C, Cs).

Example query:

%?- aitken([1], R).
%@ R = [1];
%@ R = [1, 2] ;
%@ R = [2, 3, 5] ;
%@ R = [5, 7, 10, 15] ;
%@ R = [15, 20, 27, 37, 52] a
%@ Yes

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

student

2007-04-26, 4:05 am

Markus Triska wrote:
> student <nospam@nowhere.net> writes:
>
>
> By introducing an additional argument that is used to report solutions
> incrementally, this kind of querying can be delegated to the toplevel:
>
> aitken(R, R).
> aitken(R0, R) :-
> last(R0, L),
> row(R0, L, R1),
> aitken([L|R1], R).
>
> row([], _, []).
> row([A|As], B, [C|Cs]) :-
> C is A + B,
> row(As, C, Cs).
>
> Example query:
>
> %?- aitken([1], R).
> %@ R = [1];
> %@ R = [1, 2] ;
> %@ R = [2, 3, 5] ;
> %@ R = [5, 7, 10, 15] ;
> %@ R = [15, 20, 27, 37, 52] a
> %@ Yes
>

Neat, thank you!

p.s. When is your Prolog textbook coming out? If you're aren't in
process of writing one at the moment, I hope you will think about
starting one in the not-too-distant future. I think you are also a
first-rate writer and I always look forward to reading your articles in
this newsgroup because I always seem to learn something surprising and
useful from them. You have a gift that I have only one seen before. When
I was in school, it was my privilege to have as one of my instructors a
young probability theorist from Warsaw who somehow knew how to present a
difficult proof in such a way that none of us attending his lectures
would see the conclusion coming until, at the very last moment, it
suddenly leaped out and caught us all completely by surprise, like the
punch-line if a really funny joke, and made us all break into laughter.
An amazing guy.

Cheers!

billh

student

2007-04-26, 4:05 am

student wrote:
>
> /*
> combine(*$integer, $integer, *$integer) <-- should have been
> --------------------------------------
> input: <b(1),...,b(n-1),b(n)>, c(1)
> output: <c(1),...,c(n-1),c(n)>
> */
> combine(<>, _, <> ).
> combine(<B_1]Bs_2_to_n>, C_1, <C_1]Cs_2_to_n> ) :-
> C_2 is B_1 + C_1,
> combine(Bs_2_to_n, C_2, Cs_2_to_n).
>
> */

Sponsored Links