If you are lost, talk with us [experience suggests that some of you are]
----------------------------------------------------------------------
TOPIC: pairs and lists

[NOTE: today, some non-O(1) primitives!]

Lists are incredibly useful objects.

  * Ordered sequences of stuff
    - have first, second, etc. elements.
  * Length isn't restricted.

Here's the abstraction:

CONSTRUCTOR: 
  * (pair x l) where x is an object and l is a list
      -- add x to the head of the list l.

SELECTORS:

  * head   <list> --> <object>
  * tail   <list> --> <object>, usually a <list>
  * null?  <list> --> <boolean>

CONTRACT:

  (head (pair x l)) = x
  (tail (pair x l)) = l
  (null? l) = #t  if l is the empty list, which is written '() and prints as ()
              #f  otherwise

  >> Yes, that is an unmatched single quote, which will see more
     in recitation.  Other names for '() are (list) and (quote ()).
     Lots more coming. 

Note that we had better not say 
  (head '()) and (tail '())
  * DON'T use them.
  * Dylan will express its displeasure if you do.
---------------------------------------------------------------------
Lists in Dylan are built from pairs.  We'll usually use the word "list"
to mean a PROPER LIST, or a list built from '() and pair according to the
following inductive definition:

-- '() is a proper list
-- if l is a proper list, then so is the value of (pair x l), where
     x is any <object>.

The value of (pair 1 (pair 2 (pair 3 '()))) is a proper list.
Dylan prints this as (1 2 3).
You can also specify this list as (list 1 2 3).
You can't just type (1 2 3) at Dylan [why not?]

Other examples of proper lists:

The value of:                                    is printed as:
(pair 1 (pair 2 '()))                            (1 2)
'()                                              ()
(pair "a" (pair "c" (pair "g" (pair "t" '()))))  ("a" "c" "g" "t")

But you can use pair/head/tail on objects that are not officially lists.

As far as Dylan cares:
--A <pair> is anything that can be taken apart with head/tail
--A <list> is either a <pair> or the empty list ().

Thus a Dylan <list> may not always be a proper list, but a proper list
is always a Dylan <list>.

Examples of Dylan <list>s that are not proper lists:
(pair 1 2), printed as (1 . 2)
(pair 1 (pair 2 3)), printed as (1 2 . 3)

(head (pair 1 2)) is 1
(tail (pair 1 2)) is 2

What is the difference between (pair 1 2) and (list 1 2)?

(pair 1 2) is printed (1 . 2)
(head (pair 1 2)) => 1  --its head is the number 1
(tail (pair 1 2)) => 2  --its tail is the number 2

(list 1 2) is printed (1 2)
(head (list 1 2)) => 1    --its head is the number 1
(tail (list 1 2)) => (2)  --its tail is a list of length 1 containing the number 2

Note: lists are not symmetric in head and tail!!!

(define (b <list>) (pair 1 (pair 2 (pair 3 '()))))

or alternatively,

(define (b <list>) (list 1 2 3))

THIS IS A PROPER LIST:
   () is a proper list
   so (pair 3 '()) is
   so (pair 2 (pair 3 '())) is
   so (pair 1 (pair 2 (pair 3 '()))) is
   so b is.

>> Draw box-and-pointer diagram.

b will print as (1 2 3)

IMPORTANT FACT: [useful on prelims!]
  * pair always builds exactly ONE box.

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 one reason 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 is not a special form--it evaluates its arguments

(list + 27 (+ 2 1))
  => ({add} {27} {3})

LIST 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 the list 
  (+ 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"
'exp is shorthand for (quote exp).  Can use them interchangeably.

  +  ---> {add} 
  '+ ---> +        <<-- The <symbol> +

  x  ---> whatever value x is bound to
  '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 boxes

It 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.

Q. What's the difference between (list a b c) and '(a b c)?
A. The first evals the elements, the second doesn't

(list (+ 1 2) (+ 3 4))  =>  (3 7)
'((+ 1 2) (+ 3 4))      =>  ((+ 1 2) (+ 3 4))

---------------------------------------------------------------------
Let's do some useful things with lists. 

Computing the length (number of elements) is one of the most basic
operations on a list.  It's a Dylan primitive, but let's implement
it anyway:

(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?]
[What is the running time?]

(length '(1 2 3))     => 3
(length '(1 (2 3) 4)) => 3

  * Just the number of elements in the top-level list
  * count how many tails there are till we get to the empty list.

---------------------------------------------------------------------
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 let's implement it anyway:

(define (map <function>)
  (method ((f <function>) (l <list>))
    (if (null? l)
        '()
        (pair (f (head l))
              (map f (tail l))))))

  * go down the list taking successive tails
  * pair up -- or build -- the resulting list.

Like length, map operates element-by-element, not on the primitive
elements:

(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 (list 1 2 3)) ==> (1 2 3), but it's a different list with different
boxes.

id? is a version of equality that tells if two pairs are the same box.
  * It'll be important later on.

(id? l l) => #t.

(id? l (copy l)) => #f.  prints the same, but internally it's a
different list.  Two different kinds of equality--watch out!
---------------------------------------------------------------------
Now, let's put some lists together:

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

This is again a Dylan primitive, but we could define it:

(define (append <function>)
  (method ((l1 <list>) (l2 <list>))
    (if (null? l1) 
        l2
        (pair (head l1) (append (tail l1) l2)))))

This is kind of surprising:
  * l2 doesn't get looked at!

(append '(1 2 3) '(4 5 6))
(pair {1} (append {(2 3)} {(4 5 6)}))
(pair {1} (pair {2} (append {(3)} {(4 5 6)})))
(pair {1} (pair {2} (pair {3} (pair {()} {(4 5 6)}))))
(pair {1} (pair {2} (pair {3} {(4 5 6)})))
(pair {1} (pair {2} (pair {(3 4 5 6)})))
(pair {1} {(2 3 4 5 6)})
{(1 2 3 4 5 6)}

>>> Draw box diagram, with a new 1 2 3 and the tail of the 3 pointing
>>> to the old (4 5 6)
---------------------------------------------------------------------
>>>> Possibly skip this <<<<
[Or do in section?]

How could we write something that counts the *primitive* elements in a
list structure?
  * Take apart the elements of the list too.
  * Very rarely what you want, expecially if you're building abstract types
    out of pairs.

(define (count-prim <function>)
  (method ((l <list>))
    (cond
      ((null? l) 0)
      ((atom? l) 1)
      (else: (+ (count-prim (head l))
                (count-prim (tail l)))))))

(atom? x) tells the difference between a primitive value and something
that can be taken apart with head/tail.

(define (atom? <function>)
  (method ((x <object>))
    (not (id? (object-class x) <pair>))))
---------------------------------------------------------------------
>> Skip this, or do in section <<

We can do "tree-recursion" if we want to (apply to every primitive
element in the structure rather than to every element of the list).
Called tree recursion because it is as if a tree structure, with
``leaf nodes'' that are atomic.

(define (tree-map <function>)
  (method ((f <function>) (t <list>))
    (cond
     ((null? t) '())
     ((atom? t) (f t))
     (else: (pair (tree-map f (head l))
                  (tree-map f (tail l)))))))

(tree-map (method ((x <number>)) (+ x 10)) '(1 (2 ((3)) 4)))
=> (11 (12 ((13)) 14))
---------------------------------------------------------------------

Today's stuff:
 * List structure -- pairs, with the tail being a list
   head = first
   tail = rest

 * Quotation
 * map: take successive tails of a list, building up the results using pair