1.5 Lists
Plait lists are uniform, meaning that all of the elements of a list must have the same type. The list form creates a list:
> (list 1 2 (+ 3 4)) - (Listof Number)
'(1 2 7)
> (list (string-append "a" "b") "c") - (Listof String)
'("ab" "c")
As you can see, the type of a list is written with Listof and then the type of the elements of the list. You also see that the result is printed using '. You can use a ' to create a list, but only for literal-value content (i.e., no subexpressions to evaluate):
> '(1 2 7) - (Listof Number)
'(1 2 7)
> '(1 2 (+ 3 4)) eval:70:0: typecheck failed: Symbol vs. Number
sources:
(+ 3 4)
3
+
To understand that last error message, start by observing that the ' for a literal list is the same as a the ' for a symbol. As it turns out, a ' for a list implicitly distributes the ' to each element of the list. So, '(a b) is equivalent to (list 'a 'b). It’s also the case that '(1 2 7) is equivalent to (list '1 '2 '7), because ' has no effect on a number, boolean, or string:
> '1 - Number
1
> '#t - Boolean
#t
> '"apple" - String
"apple"
> '(milk cookies) - (Listof Symbol)
'(milk cookies)
> '((pen paper) (rock scissors paper)) - (Listof (Listof Symbol))
'((pen paper) (rock scissors paper))
The expression '(1 2 (+ 3 4)) fails because that’s the same as (list 1 2 '(+ 3 4)), and '(+ 3 4) fails because it’s the same as (list '+ 3 4), but a list cannot mix a symbol with numbers.
A list is immutable. That is, the value '(1 2 3) is as
unchanging as the numbers 1, 2, and 3
within the list. You can’t change a list to add new elements to
it—
> (cons 1 '(2 3)) - (Listof Number)
'(1 2 3)
> (cons "apple" '("banana")) - (Listof String)
'("apple" "banana")
The cons operation is constant-time, because a list is internally represented as a singly linked list, and cons simply creates a new cell that contains the new value and then points to the existing list.
If you have two lists, instead of one element and a list, you can combine the lists with append:
> (append '(1 2) '(3 4)) - (Listof Number)
'(1 2 3 4)
Don’t confuse cons and append. The cons function takes an element and a list, while append takes a list and a list. That difference is reflected in their types:
> cons - ('a (Listof 'a) -> (Listof 'a))
#<procedure:cons>
> append - ((Listof 'a) (Listof 'a) -> (Listof 'a))
#<procedure:append>
Mixing them up will trigger a type error:
> (cons '(1) '(2 3)) eval:81:0: typecheck failed: (Listof Number) vs. Number
sources:
cons
2
(quote (2 3))
(quote (1))
> (append 1 '(2 3)) eval:82:0: typecheck failed: (Listof '_a) vs. Number
sources:
append
1
A list doesn’t have to contain any values:
> (list) - (Listof '_a)
'()
The empty list is so useful that it has a name: empty. Although the list form may seem fundamental, the true list-construction primitives are empty and cons, and you can build up any other list using those:
> empty - (Listof 'a)
'()
> (cons "food" empty) - (Listof String)
'("food")
> (cons "dog" (cons "food" empty)) - (Listof String)
'("dog" "food")
The empty? function determines whether a list is empty, and cons? determines whether a list has at least one item:
> (empty? empty) - Boolean
#t
> (empty? '()) - Boolean
#t
> (cons? (cons 1 '())) - Boolean
#t
> (cons? '(1)) - Boolean
#t
> (cons? empty) - Boolean
#f
> (empty? '(1)) - Boolean
#f
The cons operation constructs a new value from two pieces. The first and rest operations are the opposite of cons. Given a value produced by cons, first returns the item that cons added to the start of the list, and rest returns the list that cons added to. More generally, first gets the first item from a list, and rest gets everything list in the list when the first argument is removed.
> (first (cons 1 '(2 3))) - Number
1
> (rest (cons 1 '(2 3))) - (Listof Number)
'(2 3)
> (first '("apple" "banana" "coconut")) - String
"apple"
> (rest '("apple" "banana" "coconut")) - (Listof String)
'("banana" "coconut")
> (first (rest '("apple" "banana" "coconut"))) - String
"banana"
> (rest (rest '("apple" "banana" "coconut"))) - (Listof String)
'("coconut")
Plait also provides second, third, fourth, and list-ref. Those functions are sometimes useful to extract pieces of a list that has a known shape. Functions that take the first of a list and recur with the rest turn out to be be more common. Here’s a function that check whether "milk" is in a list of strings:
> (define (got-milk? [items : (Listof String)]) (cond [(empty? items) #f] [(cons? items) (or (string=? (first items) "milk") (got-milk? (rest items)))])) > (got-milk? empty) - Boolean
#f
> (got-milk? '("milk" "cookies")) - Boolean
#t
> (got-milk? '("cookies" "milk")) - Boolean
#t
> (got-milk? '("cookies" "cream")) - Boolean
#f