Section 2/11

Today:	Review lists functions and structure from last section.
		Introduce append.

---------------------------------------------------

Examples of cons, pair, list:

Draw box diagrams and printouts of each:
(1) (cons 'a 'b)
(2) (pair 'a 'b)
(3) (list 'a 'b)
(4) (cons 'a '())
(5) (pair 'a '(b))
(6) (list + (+ 1 2) '(+ 1 2))
(7) (cons '(a b) '(c)) (or pair...)
(8) (define l1 (cons 'a 'b))
	(head l1) --> a
	(tail l1) --> b
(9) (define l2 (list 'a 'b))
	(head l2) --> a
	(tail l2) --> (b)

Another definition for a proper list:
Repeating tail gives you '(). 
e.g. (tail (tail (tail ... (tail l)))..) --> '()

---------------------------------------------------

You've seen length and map already.

We're going to look at append.

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

How would you write append?

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

Note: don't need to look at l2

(append '(1 2 3) '(4 5 6))
(cons {1} (append {(2 3)} {(4 5 6)}))
(cons {1} (cons {2} (append {(3)} {(4 5 6)})))
(cons {1} (cons {2} (cons {3} (cons {()} {(4 5 6)}))))
(cons {1} (cons {2} (cons {3} {(4 5 6)})))
(cons {1} (cons {2} (cons {(3 4 5 6)})))
(cons {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)

What is the running time of append?