TOPIC: list structures
Lists are incredibly useful objects.
* Ordered sequences of stuff
- have first, second, etc. elements.
* Length isn't restricted.
Here's the abstraction:CONSTRUCTOR:
* cons <object>,<list> --> <list>
--- add an element to a list.
SELECTORS:
* head <list> --> <object>
* tail <list> --> <list>
* null? <list> --> <boolean>CONTRACT: (head (cons x l)) = x
(tail (cons x l)) = l
(null? l) = #t IFF l is the empty-list, which is written '() and prints as ()
>> Yes, that is an unmatched single quote, [which will see more
in recitation]. Lots more coming. Note that we don't say what
(head '()) and (tail '()) are * So, we DON'T use them.
---------------------------------------------------------------------
Lists in Dylan are built out of pairs, and there is a concrete implementation,
so There are thus THREE ways that cons/head/tail are used: * "Proper" lists
* pairs * structures combining the twoIMPORTANT FACTS:
* If L is a nonempty proper list, (tail L) MUST be a proper list.
* (tail '()) is undefined.
* A proper list is built by consing elements onto a proper list.
* Repeated TAIL eventaully gives you '()? PROPER
* Repeated TAIL eventually gives you an "atom" (something not a <pair>)
IMPROPER
Two types in Dylan
<pair>, anything that can be taken apart with head/tail
<list>, <pair> plus the empty list ()
Note that the types <list> and <pair> do not correspond to the notions
of proper or improper lists.(define (a <pair>) (cons 1 2)) or <list>
THIS IS NOT A PROPER LIST, because its tail is not a list. (tail a) is 2
(define (b <list>) (cons 1 (cons 2 (cons 3 '())))) or <pair>
THIS IS A PROPER LIST: () is a proper list so (cons 3 '()) is ...
so b is, too.>> Draw box-and-pointer diagram.
IMPORTANT FACT: [useful on prelims!] * Cons always builds exactly ONE box.
Note that in a box and pointer diagram, a pointer points to an ENTIRE box,
not (e.g. the front half). A box is
---------------------------------------------------------------------
b will print as (1 2 3)
Note that this looks a whole lot like Dylan expressions.
* It's intentional
* We'll be writing Dylan programs which manipulate Dylan
expressions. We'll be doing this in PS#3 and PS#6.
* This is why we teach in a language with uniform syntax like Dylan.
---------------------------------------------------------------------
There are lots of useful operations on lists.
LIST is a procedure which puts its arguments into a proper list
(list + 27 (+ 2 1)) --> ({add} {27} {3})
LIST isn't a special form, so all its arguments are evaluated!
[It is kind of funky, in that it takes any number of arguments.]
We're going to be building Dylan code. What if we want to build thelist
(+ 27 3)?We want to TURN OFF the evaluator temporarily.
This isn't just an issue with programming languages.Compare: "Say your name"
with "Say 'your name'"
We use a form of QUOTATION to tell the interpreter, "don't eval this".
Have seen this on symbols: 'STUFF
means, "just return something that prints like STUFF as a value" + ----> {add}
'+ ---> + <<-- The <symbol> + x ----> depends
'x ---> x <<-- The <symbol> x (+ 1 2) ---> 3
'(+ 1 2) ---> a list of three elements, which prints as (+ 1 2)
This helps our immediate problem: (list '+ 1 2) ---> (+ 1 2)Note:
(bind (((a <integer> 3)))
(list '+ a 2)) ---> (+ 3 2) [list isn't a special form!]
The elements of a list can be ANYTHING: * including lists and pairs.
(list '* (list '+ 1 2) 3) looks like this: >> Draw the boxesIt prints as
(* (+ 1 2) 3)It's a list of THREE ELEMENTS,
-- Second element is itself a LIST OF THREE ELEMENTS.
IMPORTANT FACT: [useful on prelims!]
* LIST called with N arguments builds exactly N boxes.
---------------------------------------------------------------------
Let's do some useful things with lists.
Computing the length (number of elements) is one of the most basic
operations on a list. This is a Dylan primitive, but lets see how it
can be implemented:(define (length <function>) (method ((l <list>))
(if (null? l) 0 (+ 1 (length (tail l))))))
>> What kind of process? Recursive! <<[Can you write a tail-recursive version?]
[How would you prove it correct? We'll get to that](length '(1 2 3)) == 3
(length '(1 (2 3) 4)) == 3
* Just the number of elements in the top-level list
* count how many tail's there are 'til we get to the empty list.NOTE:
* This is a non- O(1) primitive! ... What is its order of growth?
CAVEAT EMPTOR!
---------------------------------------------------------------------
Very often, you want to apply a function to each element of a list and
return a new list as a result.
(map f list) applies f to every element of list, returns result VERY POWERFUL
This is a Dylan primitive, but lets see how to implement it:
(define (map <function>) (method ((f <function>) (l <list>)) (if (null? l)
'() (cons (f (head l)) (map f (tail l))))))
* go down the list taking successive tail's
* cons up -- or build -- the resulting list.
Like length, map operates element-by-element, not on the primitiveelements:
(map length '(1 (2 3) (4 5 6) 7)) ==> (1 2 3 1)
NOTE: map is *also* a non- O(1) primitive. What is its order of growth?
---------------------------------------------------------------------
NOTE: map in Dylan can walk down several lists simultaneously.
(map + '(1 2 3) '(5 6 7)) ==> (6 8 10)
---------------------------------------------------------------------
(define (copy <function>) (method ((l <list>))
(map (method ((x <object>)) x) l)))
(copy '(1 2 3)) ==> (1 2 3), but it's a different list with differentboxes.
id? is a version of equality that tells if two pairs are the same box.
* It'll be important later on.(id? l l) ---> always true.
(id? l (copy l)) ---> always false. prints the same, but different list.
---------------------------------------------------------------------