We have seen an example of a bespoke list (the list of shapes). We could define other specific kinds of lists, but it would be painful to have to write essentially the same type definitions and functions every time we wanted to make a list of values.
Fortunately, Typed Racket has a generic (or polymorphic) list type. Most functional languages, including Racket, use lists as their primary mechanism for dealing with sequences. Therefore, they support lists as a built-in mechanism.
Let us consider the simple example of representing lists of booleans.
;; A (Listof Boolean) is either
;; - empty, (written '()) or
;; - (cons b bs), where b is a Boolean and bs is a (listof Boolean)The empty list '() and the list constructor cons come with the language.
There are corresponding predicates empty?
and cons? with type any -> Boolean. There is also a predefined
variable empty that stands for the empty list.
(: empty : Null)
(: empty? : Any -> Boolean : Null)
(: cons : (All (T) T (Listof T) -> (Listof T)))
(: cons? : Any -> Boolean : (Listof Any))The type Listof is a type constructor. The function cons is polymorphic.
|
Note
|
The types of |
Let’s write down a few lists of booleans.
empty
(cons true empty)
(cons true (cons false empty))
(cons false (cons true (cons false empty)))We can also construct lists using the quotation syntax:
'()
(list)
(list true)
'(#t)
'(#t #f)
(list false true false)While it is important you be comfortable reading the '(…) format for lists, since the
REPL will print out list values this way, it is best to avoid writing lists in this
manner yourself. This is because Racket "distributes" the quotation mark over the list
when given a list of identifiers, making them all symbols. For instance, '(true false)
becomes the same as (list 'true 'false), a list of two Symbols. This list is completely
different than (list #t #f). a list of Booleans and probably what you intended.
The functions first and rest are selectors on cons structures.
(: first : (All (T) (Listof T) -> T))
(: rest : (All (T) (Listof T) -> (Listof T)))
(: second : (All (T) (Listof T) -> T))
...
(: eighth : (All (T) (Listof T) -> T))(first '(2)) -> 2
(rest '(2)) -> '()Your program will halt with an error if you try to take, for instance, the first element of an empty list, or the seventh element of a list with only five. Thus, these functions should be used cautiously, only when the list is known to have the requisite element. Often, pattern matching with cases that cover the different possible list lengths is a more robust approach.
There are also more historical names: car, cdr.
(: car : (All (T) (Listof T) -> T))
(: cdr : (All (T) (Listof T) -> (Listof T)))We will not use these less-intuitively named versions in class, so you needn’t memorize them. We include them here just so you may recognize them if you ever encounter them.
Functions on lists
Typed Racket provides various standard operations on lists as polymorphic functions. We can compute the length of a list with
(: length : (All (X) (Listof X) -> Integer))
(check-expect (length '()) 0)
(check-expect (length '(1 2 3)) 3)Reverse the order of a list using
(: reverse : (All (X) (Listof X) -> (Listof X))
(check-expect (reverse '(1 2 3)) '(3 2 1))Two or more lists can be concatenated using the append function.
(: append : (All (X) (Listof X) * -> (Listof X)))
(check-expect (append '(1 2 3) '(4) '(5 6))
'(1 2 3 4 5 6))That star means that you can provide any number of lists to append to a
single call of append.
We can extract an element from a list by its index using
(: list-ref : (All (X) (Listof X) Integer -> X))
(check-expect (list-ref '(1 2 3) 0) 1)
(check-expect (list-ref '(1 2 3) 1) 2)
(check-expect (list-ref '(1 2 3) 2) 3)Notice that indexing starts at 0. (This convention is common across
most programming languages.) Specifying a negative index or one that
is too large results in an error.
Lastly, the make-list function creates a list of the given length, where
all of the list elements are the same value.
(: make-list : (All (X) (Integer X -> (Listof X)))
(check-expect (make-list 3 "hi") (list "hi" "hi" "hi"))