Recursively Building Lists

From: Stephen Andrew Church (sachurch_at_bigpond.com)
Date: 04/23/04

  • Next message: vannoord_at_let.rug.nl: "Re: Recursively Building Lists" 
    Date: Fri, 23 Apr 2004 00:47:27 GMT

    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

  • Next message: vannoord_at_let.rug.nl: "Re: Recursively Building Lists"

    Relevant Pages

    • Re: The empty list and the end of a list
      ... I don' t know exactly what you mean by "tail ... Maybe it is a synonym for "tail recursion", ... some recursive algorithm just aren't tail recursions. ... recursive lists). ...
      (comp.lang.lisp)
    • Re: Interesting article by Joel Spolsky: The Perils of JavaSchools
      ... >>>Lists are recursively defined structures. ... >> definition to define a list, but it isn't obligatory. ... (Pedant's observation - recursion cannot be ... Richard Harter, cri@xxxxxxxx ...
      (comp.programming)
    • Re: Lisp Question
      ... I think they use us a lot to teach recursion, ... seeing weirdly named operators and we have no abstraction capability. ... So lists are mostly what they teach, and then not well, and people come away ... I doubt many in school are teaching DEFCLASS or DEFMETHOD in classes, ...
      (comp.lang.lisp)
    • Re: set picking
      ... so i can check the answers i get with math by getting scheme to help. ... i think it's the same concept, but you got all of the recursion stuff ... The unordered subsets reduces to the known combinations problem. ... lists:. ...
      (comp.lang.scheme)
    • Re: advice from a newbie
      ... find recursion a barrier, it seemed to me to be a natural way of expressing solutions to problems. ... "To append two lists, if the first is empty the result is the same as the ... the first, all those greater than the first, sort each list, append ...
      (comp.lang.prolog)