Appending to the result of a "loop-collect" in Lisp

Question

Let's say I run the following

(loop for i to 4 collect i)

Then I get a list (0 1 2 3 4). Now, if I want to append something to the result, I may use rplacd on its last element, but since Lisp lists are linked lists, it's not very efficient. Here the list is ridiculously small, but it's only an example.

However, since the loop facility returns the list in increasing order, it has to keep track of a pointer to the last element, and update the result with rplacd, or something equivalent. A macroexpand-all shows it's what CCL does, and probably other lisps too.

Question: Is there a way to use this "pointer" in the finally clause? It would allow one to append something to the result, which is sometimes useful.

Of course, it's easy to code the pointer machinery, but it's not so nice. For example, the following will append the list e to the list (0 1 ... n).

(defun foo (n e)
    (let* ((a (list nil)) (tail a))
        (loop for i to n
              do (rplacd tail (setf tail (list i)))
              finally (rplacd tail (setf tail e))
              (return (cdr a)))))

Goodfellowship

Answer 1

An additional comparison for each iteration and one additional iteration gives you this:

CL-USER 2 > (defun foo (n e &aux (z (1+ n)))
              (loop for i to z
                    unless (= i z)
                      collect i
                    else
                      nconc e))
FOO

CL-USER 3 > (foo 4 '(f o o))
(0 1 2 3 4 F O O)

Covert

I have definitely still much to learn, especially on loop :-) – Goodfellowship

@Jean-ClaudeArbaut: Since you found out on your own that LOOP implementations keep track of the last cons and verified it macro expanding the code, it looks like you are on a good start. ;-) – Covert

I like this more than mine. It's a much cleaner solution (just add an extra iteration and do something special), and you get the implicit return of the list. This is the answer i'd accept. – Jablonski

What's the difference between this and a loop where the last clause is append e instead of nconc e? – Edrei

@ThrowawayAccount3Million: It would use a copy of the list e, which is not necessary, because we don't change it. – Covert

Answer 2

Question: Is there a way to use this "pointer" in the finally clause? It would allow one to append something to the result, which is sometimes useful.

I think the answer is "no". The syntax for the finally clause is given in:

initial-final::= initially compound-form+ | finally compound-form+ 

You can, of course, collect into some particular variable, and then append or nconc with that:

CL-USER> (loop for i from 1 to 5
              collect i into ns
              finally (return (nconc ns (list 'a 'b 'c))))
;=> (1 2 3 4 5 A B C)

That does involve an extra walk through the result, though, which may be undesirable. (I think it's what you're trying to avoid.)

Another option would be to build up the list using nconc rather than collect. If you're using collect, then you're just getting one value at a time and then collecting it. You could put that one value into a list and then "collect" it with nconc. If you save that one element list into a variable within the loop, you can refer to it, and it's pretty much a tail pointer. E.g.:

CL-USER> (loop for i from 1 to 5
            for ilist = (list i)
            nconc ilist into ns
            finally (progn 
                      (nconc ilist '(a b c))  ; ***
                      (return ns)))
;=> (1 2 3 4 5 A B C)

In the line marked with ***, the call to nconc only has to traverse the final value of ilist, i.e., (5). That's a pretty quick nconc call.

Jablonski

Nice idea, to use nconc. It's a much cleaner solution. Thank you. – Goodfellowship

It does not seem to work as nicely if nconcing happens conditionally after a when. It's still possible to do nconc (setf ilist (list i)) into ns, but in case the when clause is always false, ns is nil in the end. It would then need a subsequent (if (null ns) ...). Am I right? – Goodfellowship

@jean i think Rainer's answer is better. Do consider unaccepting this one and accepting his. – Jablonski