; more interesting scheme code:
(set! load-noisily? #t)

; data structures derived from lambda calc. directly

; a tuple, can be used for linked lists as well as other structs
(define newcell (lambda (x y) 
  (lambda (s) (if (= s 1) x y))))

(define head (lambda (cell) (cell 1)))
(define tail (lambda (cell) (cell 2)))

(define odd (newcell 1 (newcell 3 (newcell 5 (newcell 7 '())))))

;  built-in scheme operators:
;  newcell 'cons'
;  head    'car'
;  tail    'cdr'

; non-tail recursive length function
(define len (lambda (l)
   (if (equal? l '()) 0
       (+ 1 (len (tail l))))))

; tail recursive version (recursive call is last expression before exit)
; always call with (len2 odd 0)
(define len2 (lambda (l ax)
  ( if (equal? l '()) ax
       (len2 (tail l) (+ ax 1)))))

; C++ version, assuming cell is a class with tail() and head() methods:
;  int len2(cell * l, int ax)
;   { if (l == NULL) return ax;
;       else return len2(l->tail(), ax+1);
;   }

;  loop version just another form of tail-recursion
;  cell * current;
;  while (current ! = NULL)
;   { ax = ax+1;
;     current = current->tail;
;   }
;  for(cell * i=l;i!=NULL;i=i->tail) ax++;


; non-tail recursive fib function
(define fib (lambda (n)
   (if (< n 2) 1
       (+  (fib (- n 1)) (fib (- n 2))))))

; tail-recursive fib function - note the iterative function is
; defined as a LOCAL FUNCTION of the outer function

(define fib2  (lambda (n)
  ; local definition:
  (define tailfib (lambda (n a b)
    (if (< n 2) b (tailfib (- n 1) b (+ a b)))))
  ; body of outer function:
  (tailfib n 1 1)))


; length function defined on built-in lists:

(define len3 (lambda (l)
  (if (null? l) 0 (+ 1 (len3 (cdr l))))))
; doesn't look all that different, does it?!

; function to return the nth element of list l, 0th is first.
; return '() if n is too large:
(define nth (lambda (l n)
  (if (null? l) '()
    (if (< n 1) (car l)   ; note this is an "else if" expression
      (nth (cdr l) (- n 1))))))

; alternative using cond expressions, and implicit lambda
(define (nth2 l n)
  (cond ((null? l) '())
	((< n 1) (car l))
	(#t (nth (cdr l) (- n 1)))))

;(nth '(a b c d e f) 3)  -->  d
; is the above function tail-recursive?


; finds largest element L, tail-recursive version
(define (largest L ax)
  (if (null? L)  ; (equal? L '())
      ax
      (if (< ax (car L)) (largest (cdr L) (car L))
	  (largest (cdr L) ax))))

; version using cond instead of if
(define (largest L ax)
  (cond ((null? L)  ax)
        ((< ax (car L)) (largest (cdr L) (car L)))
        (#t (largest (cdr L) ax))))

; non-tail recursive version:
(define (max L) 
   (cond ((null? L) 'error)
	 ((null? (cdr L)) (car L))
	 ((> (car L) (cadr L)) (max (cons (car L) (cddr L))))
	 (#t (max (cdr L)))))

; binary search trees

;  ---------   Binary Trees  ---------

; choosing a representation:
; we could use built-in lists, for example,
; '(3 (4 () ()) (5 () ())) can represent a tree with 3 at the root and
; subtrees with data 4 and 5 on the left and right respectively, which
; in turn have empty subtrees.  Another way to have trees (or more 
; complex structures in general, is to do it with lambda encapsulation
; like we did above with "newcell", "head, and  "tail":

; node takes a datum, and left and right branches to make a tree:
; '() is again the empty tree (null)
(define node (lambda (x l r) 
    (lambda (s)
       (if (equal? s 'right) r
          (if (equal? s 'left) l x)))))

; convenient data accessors:

(define data (lambda (tree) (tree 'data)))
(define left (lambda (tree) (tree 'left)))
(define right (lambda (tree) (tree 'right)))

; computes number of nodes in the tree - try this 
; without recursion, even without tail-recursion!  
(define size (lambda (tree)
   (if (null? tree) 0
       (+ 1 (size (tree 'left)) (size (tree 'right))))))

; length of longest branch of tree
(define depth (lambda (tree)
   (if (null? tree) 0
       (let ((ldepth (depth (left tree))) 
	     (rdepth (depth (right tree))))
	 (+ 1 (if (> ldepth rdepth) ldepth rdepth))))))
; note that "if" expressions return a value, which we can then add 1 to

; determines if element x is present in the tree: - look ma, no if-else!
(define intree (lambda (x tree)
   (and (not (null? tree))
	    (or (equal? x (data tree))
		(intree x (left tree))
		(intree x (right tree))))))

(define mytree (node 6 (node 3 '() '()) (node 8 '() '())))
(define biggertree (node 9 mytree mytree))

((mytree 'left) 'data)   ; gives 3
(data (left mytree))     ; also gives 3


; prints tree elements in preorder traversal:
; here I introduce the begin construct:
; (begin A B) is the same as (labmda (x) B) A  - by virtue of 
; call by value, A is evaled first, then B. x is a dummy parameter

(define (preorder tree)
  (if (not (null? tree))
    (begin
      (display (data tree))
      (display " ")
      (preorder (left tree))
      (preorder (right tree))
    )
  )
)

(preorder biggertree)

; class excercise:  write function "smallest" that returns the
; smallest value stored in a tree - assume all values are non-negative
; integers and the empty tree has smallest value zero.