CODEWITHSUNDEEP
loopslispcommon-lisp
user1220978
user1220978

Reputation:

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

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)))))

Upvotes: 10

Views: 2769

Answers (2)

Rainer Joswig
Rainer Joswig

Reputation: 139411

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)

Upvotes: 7

Joshua Taylor
Joshua Taylor

Reputation: 85913

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.

Upvotes: 4

Related Questions