Re: O(N^2) behavior in LOOP

[Geoff Gole <geoffgole@gmail.com>]

For what it's worth, the elisp and SBCL implementations of LOOP behave
differently when the last cdr of the loop is assigned to.

; elisp
(loop for i from 1 to 3
      collecting i into x
      collecting (progn (setf (cdr (last x)) (list 'foo)) 1) into x
      finally (return x))
(1 foo 1 2 foo 1 3 foo 1)

; SBCL
(loop for i from 1 to 3
      collecting i into x
      collecting (progn (setf (cdr (last x)) (list 'foo)) 1) into x
      finally (return x))
(1 1 2 1 3 1)

The SBCL macro emits much more efficient code, but I think it's wrong.
Not that LOOP is a particuarly well defined thing to judge correctness
against.