begin traversal at the end of a list?
mera...@gmail.com
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
mera...@gmail.com wrote:
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
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
mera...@gmail.com
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.
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.
mera...@gmail.com
That's what I wanted and I said Thanks to Peter in the end of the
message.
A.L.
>
>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.
mera...@gmail.com
been addressed. Thanks for the help.
student
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
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
> student wrote:
>>...
>> RL = d(d(d(d(nil, 4), 3), 2), 1) ;
>
> 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
> 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
> 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
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
>
> /*
> combine(*$integer, $integer, *$integer) <-- should have been
Markus Triska
student <nos...@nowhere.net> writes:
> 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.
them most. It took me about a decade to implement CLP(FD) and CLP(B) in
a freely available Prolog system so that the material I want to present
can be tried out more easily by everyone who is interested.
Now, please have a look at The Power of Prolog, freely available from:
https://www.metalevel.at/prolog
The book is also available in self-hosting form, using an HTTP server
that is written in Prolog:
https://github.com/triska/the-power-of-prolog
I hope you like it. My dream is still to make Ulrich Neumerkel's GUPU
system available in a free Prolog system. I hope to achieve this in the
coming decades, possibly using a new Prolog system that is yet to come.
All the best, and take care!
Markus