Section 2/18

Today:	Even more list functions, and analysis of their running times.

---------------------------------------------------------------------------
id?:  a version of equality that test if 2 pairs are the same box.

If function copy is defined as:

(define copy 
(method ((l <list>))
(map (method ((x <object>)) x) l)))

(copy '(1 2 3)) --> (1 2 3)

but it's a different list with different boxes

(id? l l) --> #t

(id? l (copy l)) --> #f  prints the same, but it's a different list.

(= l (copy l)) --> #t  '=' checks if they "print the same".

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

Testing for membership:

(define l (list 1 2 3))

We want a function that tells us if an element is in a particular list.

(member? 1 l) --> #t
(member? 4 l) --> #f

(define (member? <function>)
	(method ((x <object>) (l <list>))
		(cond
			((null? l) #f)
			((= (head l) x) #t)
			(else:
				(member? x (tail l))))))



Reversing a list:

Want a function that does:

(reverse '(1 2 3)) --> (3 2 1)

(define (reverse <function>)
	(method ((l <list>))
		(if (null? l)
		    '()
		    (append (reverse (tail l))
				(list (head l))))))

Running time for this implementation of reverse:

What's the recurrence relation?

T(0) = c0
T(n) = c1 + (n-1) + T(n-1)

So T(n) = n(c1) + sum(n-i), i goes from 1 to n.

But sum(n-i), i goes from 1 to n , is the same as sum(i), i goes from n-1.  
Both equal (n-1)(n)/2 --> O(n^2).

Can we do better than O(n^2)?


A tail-recursive linear version:
(define reverse2
	(method ((l <list>))
		(bind-methods ((iter ((result <list>) (l <list>))
			(if (null? l)
			    result
			    (iter (cons (head l) result)
				    (tail l)))))
		  (iter '() l))))