6 ms·

Isn't prepending the efficient operation? Appending would require mutation or copying, prepending only requires a single new cons cell. Appending to a linked l

Isn't prepending the efficient operation? Appending would require mutation or copying, prepending only requires a single new cons cell. Appending to a linked list is fine if you can mutate and keep a pointer to the tail, but then again, extending mutable arrays is also amortized O(1) assuming a reasonable allocation scheme.

brabel 3y ago
The common pattern in LISP is to prepend using cons and then reverse the list at the end if order matters. Check this program as an example: http://www.norvig.com/java-lisp.html http://www.norvig.com/java-lisp.html Recursion is done with `(cons (nth-digit digits start) words)` and recursion ends with `(format t "~a:~{ ~a~}~%" num (reverse words))`.
- lispm 3y ago
  Another common pattern is to keep track of the last cons and add there. This saves the reverse operation. (loop for i in some-list when (evenp i) collect i) will do something like that behind the scenes.
  - brabel 3y ago
    I don't understand how that works. (reverse) changes every cons cell in order to make each cell point in the "opposite" direction. Do you have a reference I can check?
    - lispm 3y ago
      Imagine, we want to write a function which returns a list of numbers from 0 below N. This is just an illustration of the iteration principles. One could use a numeric loop, push each number to the front and return the reversed result list: (defun iota (n &aux result) (dotimes (i n (nreverse result)) (push i result))) But we can also use: (defun iota (n &aux (result (list nil)) (pointer result)) (dotimes (i n (cdr result)) (setf (cdr pointer) (list i) pointer (cdr pointer)))) As you can see, there is no REVERSE needed. Instead the pointer is moved to mark the cons where to add the next cons+item.
      - brabel 3y ago
        Oh I see. You keep track of the last cons * on each iteration * :) (this last bit was missing). Interesting, thanks for showing it.

brabel 3y ago

The common pattern in LISP is to prepend using cons and then reverse the list at the end if order matters. Check this program as an example: http://www.norvig.com/java-lisp.html http://www.norvig.com/java-lisp.html Recursion is done with `(cons (nth-digit digits start) words)` and recursion ends with `(format t "~a:~{ ~a~}~%" num (reverse words))`.

lispm 3y ago
Another common pattern is to keep track of the last cons and add there. This saves the reverse operation. (loop for i in some-list when (evenp i) collect i) will do something like that behind the scenes.
- brabel 3y ago
  I don't understand how that works. (reverse) changes every cons cell in order to make each cell point in the "opposite" direction. Do you have a reference I can check?
  - lispm 3y ago
    Imagine, we want to write a function which returns a list of numbers from 0 below N. This is just an illustration of the iteration principles. One could use a numeric loop, push each number to the front and return the reversed result list: (defun iota (n &aux result) (dotimes (i n (nreverse result)) (push i result))) But we can also use: (defun iota (n &aux (result (list nil)) (pointer result)) (dotimes (i n (cdr result)) (setf (cdr pointer) (list i) pointer (cdr pointer)))) As you can see, there is no REVERSE needed. Instead the pointer is moved to mark the cons where to add the next cons+item.
    - brabel 3y ago
      Oh I see. You keep track of the last cons * on each iteration * :) (this last bit was missing). Interesting, thanks for showing it.