Prolog - Recursively Building Lists

Author

Recursively Building Lists

Stephen Andrew Church

2004-04-22, 9:38 pm

Greetings,

I would very much appreciate some help in understanding how it is one
constructs lists recursively. I believe I have a reasonable grasp of how
lists may be traversed recursively by passing the list tail as an argument
in succesive recursive calls, and terminating the recursion with a match to
an empty list argument.

However, I have experienced considerable difficulty in going the opposite
way, so to speak, constructing a list recursively. Here is the code I have
been using.

%% Both these predicates have been used with the same result
genlist(0,L0,L0).
%%genlist(0,L0,L1) :- !, L0 = L1.

genlist(N0,L0,L1) :- addtoend(L0,N0,L1), N1 is N0-1,
genlist(N1,L1,L2).

addtoend([],E0,[E0]).
addtoend([H0|T0],E0,[H0|T1]) :- addtoend(T0,E0,T1).

If I submit the query.

genlist(5, [], L).

L is only ever instantiated to [5], and the whole of the constructed list,
[1,2,3,4,5], is not returned.

If a patient soul could please explain not only where I am in error, but
describe the usual or commonly accepted recursive technique for performing a
task such as this, I would be immensely grateful.

Stephen

vannoord@let.rug.nl

2004-04-23, 3:33 am

Stephen Andrew Church <sachurch@bigpond.com> wrote:
> Greetings,

> I would very much appreciate some help in understanding how it is one
> constructs lists recursively. I believe I have a reasonable grasp of how
> lists may be traversed recursively by passing the list tail as an argument
> in succesive recursive calls, and terminating the recursion with a match to
> an empty list argument.

> However, I have experienced considerable difficulty in going the opposite
> way, so to speak, constructing a list recursively. Here is the code I have
> been using.

> %% Both these predicates have been used with the same result
> genlist(0,L0,L0).
> %%genlist(0,L0,L1) :- !, L0 = L1.

> genlist(N0,L0,L1) :- addtoend(L0,N0,L1), N1 is N0-1,
> genlist(N1,L1,L2).

the "resulting" list L2 does not occur in the head of the clause. What
you wanted:

> genlist(N0,L0,L2) :- addtoend(L0,N0,L1), N1 is N0-1,
> genlist(N1,L1,L2).

however, this is still rather a cumbersome way to do this, since you
traverse the list over and over again.

Your assumption that 'traversing' and 'generating' lists are different
things is, in Prolog, wrong. You could define genlist/3 as if it *checks*
whether a given list is according to your liking. As a side-effect, it
will 'generate' the list if it happened to be unbound.

Here's how I would do it:

%% genlist(+N,?List) % List is a list of integers 1..N
genlist(N,List) :-
genlist(0,N,List).

genlist(N,N,[]).
genlist(N0,N,[N1|Rest]) :-
N0 =< N,
N1 is N0 + 1,
genlist(N1,N,Rest).

(untested)

Gj

--
Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl http://www.let.rug.nl/~vannoord

Nameless

2004-04-23, 1:38 pm

"Stephen Andrew Church" wrote:
> I would very much appreciate some help in understanding how it
> is one constructs lists recursively. I believe I have a
> reasonable grasp of how lists may be traversed recursively by
> passing the list tail as an argument in succesive recursive
> calls, and terminating the recursion with a match to an empty
> list argument.
>
> However, I have experienced considerable difficulty in going
> the opposite way, so to speak, constructing a list recursively.
> Here is the code I have been using.
>
> %% Both these predicates have been used with the same result
> genlist(0,L0,L0).
> %%genlist(0,L0,L1) :- !, L0 = L1.
>
> genlist(N0,L0,L1) :- addtoend(L0,N0,L1), N1 is N0-1,
> genlist(N1,L1,L2).
>
> addtoend([],E0,[E0]).
> addtoend([H0|T0],E0,[H0|T1]) :- addtoend(T0,E0,T1).
>
> If I submit the query.
>
> genlist(5, [], L).
>
> L is only ever instantiated to [5], and the whole of the
> constructed list, [1,2,3,4,5], is not returned.
>
> If a patient soul could please explain not only where I am in
> error, but describe the usual or commonly accepted recursive
> technique for performing a task such as this, I would be
> immensely grateful.

As an aside, you may be interested to know that most Prolog
implementations provide a built-in predicate to generate
and/or test an integer sequence, namely between/3 (or for/3).

--
Mail sent to this email address is automatically deleted
(unread) on the server. Send replies to the newsgroup.

bart demoen

2004-04-24, 6:35 pm

Nameless wrote:

> As an aside, you may be interested to know that most Prolog
> implementations provide a built-in predicate to generate
> and/or test an integer sequence, namely between/3 (or for/3).

Hmm ... there are currently 10 Prolog systems easily accessible to me
and using for/3 at the toplevel results in error messages (or in one
case silent failure) for all;
using between/3 at the toplevel ... the same, except for SWI-Prolog
that seems to recognise this predicate.

These 10 Prolog systems are:
SICStus Yap SWI XSB GNU ECLiPse ilProlog hProlog B-Prolog CIAO

So, you must know about at least 9 other Prolog systems in which
between/3 or for/3 is a built-in.
Let me give you a discount of 2, because ilProlog and hProlog are
not in use widely.
Could you list those (at least) 7 then ? Thank you.

Bart Demoen

Nameless

2004-04-24, 8:31 pm

"bart demoen" wrote in message
news:1082842408.263033@seven.kulnet.kuleuven.ac.be...
> Nameless wrote:
>
>
> Hmm ... there are currently 10 Prolog systems easily accessible to
me
> and using for/3 at the toplevel results in error messages (or in one
> case silent failure) for all;
> using between/3 at the toplevel ... the same, except for SWI-Prolog
> that seems to recognise this predicate.
>
> These 10 Prolog systems are:
> SICStus Yap SWI XSB GNU ECLiPse ilProlog hProlog B-Prolog CIAO
>
> So, you must know about at least 9 other Prolog systems in which
> between/3 or for/3 is a built-in.
> Let me give you a discount of 2, because ilProlog and hProlog are
> not in use widely.
> Could you list those (at least) 7 then ? Thank you.

Ok, Smart Ass, you caught me out there! :-) I should have
said: supplied library predicate.

--
Mail sent to this email address is automatically deleted
(unread) on the server. Send replies to the newsgroup.

Sponsored Links