I wish I could, some day, eventually understand why (())))(()(())))) is “the only computer language that is beautiful” (Neal Stephenson).

Tools

Visualize list using CS 61A Code with (autodraw) command.

List is the core in Scheme, a dialect of Lisp - but its nesting relationship can be really frustrating. This post aims to address the issue about the list.

List Constructor

So, apparently these four options:

scm> (cons 2 (cons 3 (cons 4 nil)))
(2 3 4)
scm> (list 2 3 4)
(2 3 4)
scm> '(2 3 4)
(2 3 4)
scm> (quote (2 3 4))
(2 3 4)

all do the same thing.

  • You cannot do (cons 1 2) or (cons 1 2 3). `cons` only accepts two argument and the second has to be either `nil` or another list.
  • (list 2 3 4) is somewhat like the syntax sugar for the linked-list-styled constructor cons.
  • The last two work because of symbol types (I would write a separate post on Scheme Symbol Type). But for our purpose here all we need to know is that they work. You could use them as regular list - for example, storing them as variable:
scm> (define lst (quote (2 3 4)))
lst
scm> lst
(2 3 4)

Next up, nesting:

scm> '((1 2) (3 4) 5)
((1 2) (3 4) 5)
scm> (quote ((1 2) (3 4) 5))
((1 2) (3 4) 5)
scm> (list (list 1 2) (list 3 4) 5)
((1 2) (3 4) 5)
scm> (cons (cons 1 (cons 2 nil)) (cons (cons 3 (cons 4 nil)) (cons 5 nil)))
((1 2) (3 4) 5)

Really, no new rule to be said - if you walk through these codes you would find that they just obey everything we said above in the non-nesting case. Just be really careful about the parentheses, and avoid the insane cons as far as possible.

One more thing: be careful when you mix and match:

scm> (list (cons 1 (cons 2 nil)) '(3 4) 5) ;this is ok
((1 2) (3 4) 5)
scm> '((1 2) (list 3 4) 5) ;this is not ok - the quote would quote the whole thing
((1 2) (list 3 4) 5)

Element Retrieve

We could use car and cdr. No indexing.

scm> (define lst (list 1 2))
lst

;car returns the first element
scm> (car lst)
1

;cdr returns a list, which contains all elements from the rest of the list, even if the rest of the list only has one element or is empty.
scm> (cdr lst)
(2)

;These still work on an one-element list
scm> (define a (cdr lst))
a
scm> (car a)
2
scm> (cdr a)
()
scm> (define b (cdr a))
b

;They don't work on an empty list
scm> (car b) ;Error: argument 0 of car has wrong type (nil)
scm> (cdr b) ;Error: argument 0 of cdr has wrong type (nil)

;So, test empty list with this:
scm> (null? b)
#t

Those are the basics for car and cdr (Seriously, why don’t we just call them “first” and “rest”?).

Here comes the ugly part:

scm> (define nest '(1 ((2 (3)) 4) (5 6) 7))
nest
;ok, how do you get 3 out?
scm> (cdr (car (car (cdr nest))))
((3))
scm> (car (cdr (car (car (cdr nest)))))
(3)
scm> (car (car (cdr (car (car (cdr nest))))))
3 ;finally!

Again, no new rules. Just nesting. Just be careful with parentheses. Also - think clearly about whether you are getting a one-element list or the element.

List Modifications

; set-car! and set-cdr! do what you think they do
scm> (define a '(1 2 3))
a
scm> (set-car! a 4)
scm> a
(4 2 3)
scm> (set-cdr! a '(5))
scm> a
(4 5)

Remember to pass in a list or nill for set-cdr! Again, if you pass an element as the second element you get a pair. (set-car a 5) gives you (4 . 5).

Now, pay close attention to append procedure:

scm> (append '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)

append should be called on two lists. (append 2 3) gives you an error; (append (list 2) 3) gives you a pair (2 . 3).

More importantly - the Scheme append is not Python append. Rather, it is Python extend. How do you do a Python append? Use cons!

Other List Procedures

“Procedure” in scheme is “function” in Python.

;We talked about this before
scm> (null? nil)
#t
;Same as Python len()
scm> (length '(1 2 3 4 5))
5
scm> (length '(1 ((2 (3)) 4) (5 6) 7))
4 ;only checks down one layer