1.5Lists🔗 i

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 12(+ 34))

- (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):

> '(127)

- (Listof Number)

'(1 2 7)

> '(12(+34))

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, '(ab) is equivalent to (list 'a'b). It’s also the case that '(127) 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"

> '(milkcookies)

- (Listof Symbol)

'(milk cookies)

> '((penpaper)(rockscissorspaper))

- (Listof (Listof Symbol))

'((pen paper) (rock scissors paper))

The expression '(12(+34)) fails because that’s the same as (list 12'(+34)), and '(+34) fails because it’s the same as (list '+34), but a list cannot mix a symbol with numbers.

A list is immutable. That is, the value '(123) 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—but you can create a new list that is like the old one, except that it has another element. The cons function takes an element and a list and “adds” the element to the front of the list, creating a new list with all of the elements:

> (cons 1'(23))

- (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 '(12)'(34))

- (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)'(23))

eval:81:0: typecheck failed: (Listof Number) vs. Number

sources:

cons

2

(quote (2 3))

(quote (1))

> (append 1'(23))

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'(23)))

- Number

1

> (rest (cons 1'(23)))

- (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