5 ms·

I've been trying to learn CL by using it to do AOC. As someone coming from mostly Python, there is a lot about it that confuses and, occasionally, frustrates me

I've been trying to learn CL by using it to do AOC. As someone coming from mostly Python, there is a lot about it that confuses and, occasionally, frustrates me. Maybe I'm just missing something obvious but it doesn't seem like you can start with an empty list that you can repeatedly append to. The empty list is nil, and `(append nil foo)` seems to just yield `foo`, not `(list foo)`. So trying to append to that object will (probably) raise an error.

aidenn0 4y ago
Lists in python are what are called vectors in almost every other language. You can make a resizable vector in CL and use vector-push-extend to do things just like python.
shadowgovt 4y ago
In LISP, the cheap / straightforward operation is attaching things to the front of a list. Appending to the rear of a list is (usually) going to be the more expensive operation (naively, doing so requires walking all the way to the end of the list, because lists are more like linked list constructs than arrays that silently resize as needed).
martinflack 4y ago
APPEND is for concatenating two lists. If you're trying to add a value, then if your NIL is already in a variable, use PUSH to add the value (to the front). This will build the result list in reverse, so you can NREVERSE it at the end.
- User23 4y ago
  There’s a relatively straightforward deque implementation too if you need to append in addition to pushing. It can require a little rebalancing, but I imagine it amortizes to constant time.
tuukkah 4y ago
append concatenates lists so you'd need (append nil '(foo))
- DonaldFisk 4y ago
  It actually leaves both its arguments unaltered and creates a new list. There's another function called nconc which does concatenate them, changing its first argument to the new list (unless its first argument is NIL).
  - aidenn0 4y ago
    Note that append does not copy the last argument, so there is structure sharing when you use it.
gus_massa 4y ago
I think what you want to do is (cons 'foo nil) It's in the oposite order. It starts with the empty list and it adds foo in the head. An extension is (cons 'bar (cons 'foo nil)) that is equivalent to (list 'bar 'foo)
DonaldFisk 4y ago
The easiest way to think about this, as Tim mentions in his article, is that in Common Lisp, you can write nil as '(), so if foo is defined as the list (d e f), (append nil foo) is equivalent to (append '() '(d e f)) which more obviously evaluates to (d e f), just as (append '(a b c) '(d e f)) evaluates to (a b c d e f). It's better to think of Lisp append's first argument being appended onto its second: (append '(a b) '(c d)) => (cons 'a (append '(b) '(c d))) => (cons 'a (cons 'b (append '() '(c d)))) => (cons 'a (cons 'b '(c d))) => (cons 'a '(b c d)), which evaluates to (a b c d). The lists '(a b) and '(c d) are still unaltered at the end of the computation, and a new list '(a b c d) is returned by the call to append.
todd8 4y ago
What is AOC? It’s hard to keep up with all the acronyms.
- Thiez 4y ago
  https://adventofcode.com/ https://adventofcode.com/
  - todd8 4y ago
    Thanks I was just on that website!
TheOtherHobbes 4y ago
There's a huge amount of documentation telling you that NIL is an empty list. It isn't. It has none of the mechanics of an empty list in Python etc. It's more like a null link, and has quite a bit in common with /0 as a string terminator. It does different things on its own and in the context of a list. The key is that Lisp list items are stored as car (link/pointer to an item) and cdr (link to the next item/s in the list) pairs. Lisp's dot notation makes this explicit, but it's hidden behind syntactic sugar because it's messy and hard to read. (a b c) is really (a . (b . (c . NIL))) Each dot shows the cdr of the preceding car. On its own NIL is just a constant. It has no listy features - specifically no slots for car or cdr values. Although you can do things like (length NIL) you can't change it. It's simply not a list. You can add car/cdr pointers to it with cons. Now you can use NIL in a list. You can use NIL as a cdr list terminator. (something . NIL) means the list is over. There are no more cdrs after it. You can use NIL as an empty car placeholder. (NIL . something) means the car has no value, but the list continues onwards with a cdr link. In your example (append NIL foo) actually returns (foo . NIL). NIL is being used as a cdr terminator. Lisp hides the ". NIL" because syntactic sugar. If you (append NIL foo) again, you still get (foo) because NIL already terminates the list and there's no reason to add another NIL after it. (push foo NIL) throws an error because push is destructive and is attempting to change NIL. Which isn't allowed. (cons NIL a) gives you (NIL a) because NIL is being prepended as an empty car pointer. Which is how you get NILs into a list without it collapsing around itself. It's just like any other list item, except it has a null value. The list can continue past it into further cdrs in the usual way. Anyway. This is confusing because you have a single symbol doing three different things in three different contexts. (Not even counting its use as a Boolean...) Worse, syntactic sugar and the various function internals hide this from you. And the documentation tells you something that isn't true. So unless you look at the source and/or learn how the various functions understand and use NIL you will be confused. The up side is a REPL is interactive and easy to play with, so it's not a huge effort to experiment and see what falls out.
- costigan 4y ago
  > NIL is an empty list.... It isn't. It has none of the mechanics of an empty list in Python etc. I can see how NIL is confusing when coming from Python, but I think this comment has it backwards. The idea of lists as chains or trees of pointers with a distinguished termination value predates LISP by a few years. Moreover, this kind of list predates Python's use of the term by more than 35 years. If you treat lists as just a particularly useful subclass of trees of CONS cells, then they and NIL make perfect sense. Python's lists are fine too, they're just a different kind of thing.
hayley-patton 4y ago
> Maybe I'm just missing something obvious but it doesn't seem like you can start with an empty list that you can repeatedly append to You can, but appending some list L and an empty list, or an empty list and L yields L in either case; there's nothing to append. Subsequent appends will be more interesting, e.g. CL-USER> (append '(x) (append '(y z) '())) (X Y Z) > The empty list is nil, and `(append nil foo)` seems to just yield `foo`, not `(list foo)` Right. Conceptually APPEND appends lists and not bare elements; try (append '() '(foo))
Jtsummers 4y ago
`append` on lists is equivalent to concatenation, not Python's append which is equivalent to `vector-push` or `vector-push-extend` in Lisp (and which, as the name suggests, takes a vector for the place and not a list). For performance reasons, the more conventional behavior in Lisp to collect values would be: (let ((some-place nil)) (push an-item some-place) ... (nreverse some-place)) ;; if the order really matters, you see the same pattern in Erlang and others Pushing (and popping) work on the front of lists. Counterintuitively, vector-push and vector-pop work on the end of the vector (though the rationale around performance is the same,). By pushing/popping on the front of the list the action can be done in constant time. `push item place` is equivalent to this whether it's precisely this under the hood for an implementation or not: (setf place (cons item place)) Pop is this: (prog1 (car place) (setf place (cdr place))) (Maybe I've been spending too much time in the hyper spec, my equivalence examples could have been copy/pasted from it and I wrote them before double checking.) Pop: http://clhs.lisp.se/Body/m_pop.htm#pop http://clhs.lisp.se/Body/m_pop.htm#pop Push: http://clhs.lisp.se/Body/m_push.htm#push http://clhs.lisp.se/Body/m_push.htm#push
- lispm 4y ago
  > For performance reasons, the more conventional behavior in Lisp to collect values would be What you describe is what a human typical would write. For tools this is optimized. For example in (loop for e in list collect (oddp e)) this usually would be optimized. It would not add to the end and then reverse. Instead, it would keep a pointer to the end and add to the end via that pointer.
  - kagevf 4y ago
    Would the code to maintain a pointer on the last element look something like this? (let* ((list (list 1 2 3 4)) (last (last list))) (rplacd last (list 5 6)) (setf last (last last)) (format t "list: ~a~%last: ~a~%" list last)) => list: (1 2 3 4 5 6) last: (6)
    - lispm 4y ago
      in an iteration: (let* ((rlist (list '())) (last list)) (flet ((collect (item) (setf (cdr last) (list item) last (cdr last)) item) (finish () (cdr rlist))) (dotimes (i 10) (collect i)) (finish)))

aidenn0 4y ago

Lists in python are what are called vectors in almost every other language. You can make a resizable vector in CL and use vector-push-extend to do things just like python.

shadowgovt 4y ago

In LISP, the cheap / straightforward operation is attaching things to the front of a list. Appending to the rear of a list is (usually) going to be the more expensive operation (naively, doing so requires walking all the way to the end of the list, because lists are more like linked list constructs than arrays that silently resize as needed).

martinflack 4y ago

APPEND is for concatenating two lists. If you're trying to add a value, then if your NIL is already in a variable, use PUSH to add the value (to the front). This will build the result list in reverse, so you can NREVERSE it at the end.

User23 4y ago
There’s a relatively straightforward deque implementation too if you need to append in addition to pushing. It can require a little rebalancing, but I imagine it amortizes to constant time.

tuukkah 4y ago

append concatenates lists so you'd need (append nil '(foo))

DonaldFisk 4y ago
It actually leaves both its arguments unaltered and creates a new list. There's another function called nconc which does concatenate them, changing its first argument to the new list (unless its first argument is NIL).
- aidenn0 4y ago
  Note that append does not copy the last argument, so there is structure sharing when you use it.

gus_massa 4y ago

I think what you want to do is (cons 'foo nil) It's in the oposite order. It starts with the empty list and it adds foo in the head. An extension is (cons 'bar (cons 'foo nil)) that is equivalent to (list 'bar 'foo)

DonaldFisk 4y ago

The easiest way to think about this, as Tim mentions in his article, is that in Common Lisp, you can write nil as '(), so if foo is defined as the list (d e f), (append nil foo) is equivalent to (append '() '(d e f)) which more obviously evaluates to (d e f), just as (append '(a b c) '(d e f)) evaluates to (a b c d e f). It's better to think of Lisp append's first argument being appended onto its second: (append '(a b) '(c d)) => (cons 'a (append '(b) '(c d))) => (cons 'a (cons 'b (append '() '(c d)))) => (cons 'a (cons 'b '(c d))) => (cons 'a '(b c d)), which evaluates to (a b c d). The lists '(a b) and '(c d) are still unaltered at the end of the computation, and a new list '(a b c d) is returned by the call to append.

todd8 4y ago

What is AOC? It’s hard to keep up with all the acronyms.

Thiez 4y ago
https://adventofcode.com/ https://adventofcode.com/
- todd8 4y ago
  Thanks I was just on that website!

TheOtherHobbes 4y ago

There's a huge amount of documentation telling you that NIL is an empty list. It isn't. It has none of the mechanics of an empty list in Python etc. It's more like a null link, and has quite a bit in common with /0 as a string terminator. It does different things on its own and in the context of a list. The key is that Lisp list items are stored as car (link/pointer to an item) and cdr (link to the next item/s in the list) pairs. Lisp's dot notation makes this explicit, but it's hidden behind syntactic sugar because it's messy and hard to read. (a b c) is really (a . (b . (c . NIL))) Each dot shows the cdr of the preceding car. On its own NIL is just a constant. It has no listy features - specifically no slots for car or cdr values. Although you can do things like (length NIL) you can't change it. It's simply not a list. You can add car/cdr pointers to it with cons. Now you can use NIL in a list. You can use NIL as a cdr list terminator. (something . NIL) means the list is over. There are no more cdrs after it. You can use NIL as an empty car placeholder. (NIL . something) means the car has no value, but the list continues onwards with a cdr link. In your example (append NIL foo) actually returns (foo . NIL). NIL is being used as a cdr terminator. Lisp hides the ". NIL" because syntactic sugar. If you (append NIL foo) again, you still get (foo) because NIL already terminates the list and there's no reason to add another NIL after it. (push foo NIL) throws an error because push is destructive and is attempting to change NIL. Which isn't allowed. (cons NIL a) gives you (NIL a) because NIL is being prepended as an empty car pointer. Which is how you get NILs into a list without it collapsing around itself. It's just like any other list item, except it has a null value. The list can continue past it into further cdrs in the usual way. Anyway. This is confusing because you have a single symbol doing three different things in three different contexts. (Not even counting its use as a Boolean...) Worse, syntactic sugar and the various function internals hide this from you. And the documentation tells you something that isn't true. So unless you look at the source and/or learn how the various functions understand and use NIL you will be confused. The up side is a REPL is interactive and easy to play with, so it's not a huge effort to experiment and see what falls out.

costigan 4y ago
> NIL is an empty list.... It isn't. It has none of the mechanics of an empty list in Python etc. I can see how NIL is confusing when coming from Python, but I think this comment has it backwards. The idea of lists as chains or trees of pointers with a distinguished termination value predates LISP by a few years. Moreover, this kind of list predates Python's use of the term by more than 35 years. If you treat lists as just a particularly useful subclass of trees of CONS cells, then they and NIL make perfect sense. Python's lists are fine too, they're just a different kind of thing.

hayley-patton 4y ago

> Maybe I'm just missing something obvious but it doesn't seem like you can start with an empty list that you can repeatedly append to You can, but appending some list L and an empty list, or an empty list and L yields L in either case; there's nothing to append. Subsequent appends will be more interesting, e.g. CL-USER> (append '(x) (append '(y z) '())) (X Y Z) > The empty list is nil, and `(append nil foo)` seems to just yield `foo`, not `(list foo)` Right. Conceptually APPEND appends lists and not bare elements; try (append '() '(foo))

Jtsummers 4y ago

`append` on lists is equivalent to concatenation, not Python's append which is equivalent to `vector-push` or `vector-push-extend` in Lisp (and which, as the name suggests, takes a vector for the place and not a list). For performance reasons, the more conventional behavior in Lisp to collect values would be: (let ((some-place nil)) (push an-item some-place) ... (nreverse some-place)) ;; if the order really matters, you see the same pattern in Erlang and others Pushing (and popping) work on the front of lists. Counterintuitively, vector-push and vector-pop work on the end of the vector (though the rationale around performance is the same,). By pushing/popping on the front of the list the action can be done in constant time. `push item place` is equivalent to this whether it's precisely this under the hood for an implementation or not: (setf place (cons item place)) Pop is this: (prog1 (car place) (setf place (cdr place))) (Maybe I've been spending too much time in the hyper spec, my equivalence examples could have been copy/pasted from it and I wrote them before double checking.) Pop: http://clhs.lisp.se/Body/m_pop.htm#pop http://clhs.lisp.se/Body/m_pop.htm#pop Push: http://clhs.lisp.se/Body/m_push.htm#push http://clhs.lisp.se/Body/m_push.htm#push

lispm 4y ago
> For performance reasons, the more conventional behavior in Lisp to collect values would be What you describe is what a human typical would write. For tools this is optimized. For example in (loop for e in list collect (oddp e)) this usually would be optimized. It would not add to the end and then reverse. Instead, it would keep a pointer to the end and add to the end via that pointer.
- kagevf 4y ago
  Would the code to maintain a pointer on the last element look something like this? (let* ((list (list 1 2 3 4)) (last (last list))) (rplacd last (list 5 6)) (setf last (last last)) (format t "list: ~a~%last: ~a~%" list last)) => list: (1 2 3 4 5 6) last: (6)
  - lispm 4y ago
    in an iteration: (let* ((rlist (list '())) (last list)) (flet ((collect (item) (setf (cdr last) (list item) last (cdr last)) item) (finish () (cdr rlist))) (dotimes (i 10) (collect i)) (finish)))