12

What's the difference between using cons to combine an element to a list and using cons to combine a list to an element in scheme?

Furthermore, how exactly does cons work? Does it add element to the end of the list or the beginning?

Thanks!

Rainer Joswig
  • 136,269
  • 10
  • 221
  • 346
Maritha Wang
  • 175
  • 1
  • 2
  • 8
  • 2
    @ÓscarLópez's answer explains this pretty well. It's helpful to realize that in the Lisp family of languages it's not quite right to think of `cons` as a _list_ operation. Lisp languages typically have _cons cells_ as genuine datatypes and then implement lists as _intensional datatypes_. The things that we call lists are lists _by convention_. I mentioned this in [an earlier answer](http://stackoverflow.com/a/19126410/1281433) while describing how we can often cons cells to _implement_ lists, but how we can also cons cells to implement other structures, such as trees. – Joshua Taylor Oct 07 '13 at 13:46
  • @JoshuaTaylor Page Not found. – Han Qiu Aug 09 '16 at 07:16
  • @hanQiu I guess that question got deleted. But there's a section in SO documentation now that covers the same idea: [lists as a convention](http://stackoverflow.com/documentation/common-lisp/2622/cons-cells-and-lists/8700/lists-as-a-convention#t=201608091045099806348) – Joshua Taylor Aug 09 '16 at 10:47
  • 1
    That documentation _also_ got deleted :( – Óscar López Feb 20 '19 at 16:43

1 Answers1

30

The primitive cons simply sticks together two things, the fact that some of those things are considered lists is incidental. For instance, this works and creates a pair (also known as a cons cell):

(cons 1 2)
=> '(1 . 2)     ; a pair

Now, if the second argument to cons happens to be a list, then the result will be a new list, and the first argument to cons will be added at the head of the old list. In other words: to create a list you need a list, even if it's empty:

(cons 1 '(2 3))
=> '(1 2 3)     ; a list

(cons 1 (cons 2 '()))
=> '(1 2)       ; a list

(cons 1 '())
=> '(1)         ; a list

But if the second argument to cons is not a list, then the result will be just a pair, or an improper list, meaning that it doesn't end in '() as it should to be considered a list:

(cons '(1 2) 3)
=> '((1 2) . 3) ; a pair, not a list

(cons 1 (cons 2 3))
=> '(1 2 . 3)   ; an improper list

Just to clarify, you can't use cons to add elements at the end of a list. The usual way to build a list is going from right-to-left, adding elements in reverse at the head position - say you want to build the list '(1 2 3), then you have to cons the elements in the order 3 2 1:

(cons 3 '())                   ; list is '(3)
(cons 2 (cons 3 '()))          ; list is '(2 3)
(cons 1 (cons 2 (cons 3 '()))) ; list is '(1 2 3)

For those rare occasions where you need to add one element at the end (and believe me, doing so generally means that you're thinking the algorithm wrong) you can use append, which receives two lists as arguments:

(append '(1 2 3) '(4))
=> '(1 2 3 4)
Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • When I try (append '() a), I am getting simply 'a. Can you please explain why so? – Sreekumar R Sep 04 '21 at 09:25
  • 1
    Check the [docs](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._append%29%29) – Óscar López Sep 04 '21 at 09:27
  • I asked you after looking into docs. Manual says, v any/c can be added to list. But it is not telling this peculiar behavior. What will happen if I append an atom to an empty list. My understanding is that we should get a list with one element (just appended). – Sreekumar R Sep 04 '21 at 10:45
  • 1
    The relevant part is: "The last argument need not be a list, in which case the result is an “improper list.”". With an empty list as the first argument, it just returns the second argument. In general: the last argument is returned as-is and becomes the last element in the returned list; it can be of any type. All the other arguments must be lists and if they're empty they're ignored. – Óscar López Sep 04 '21 at 12:05
  • Thanks for the clarification. Sorry to trouble you without properly reading documentation. – Sreekumar R Sep 04 '21 at 12:37