recitation 10: symbols, sentences & binary trees

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

* what's the difference between a string & a symbol?
  - strings can have spaces
  - symbols must be legal names (can't start with a number,
    can't have spaces or some special characters)
  - strings are used & printed inside of double quotes 
  - symbols print without quotes

* why do we need both?
  - by using symbols we can make things that print out like 
    valid scheme expressions

------------------------------------------------------
Application:  Writing Sentences

; <sentence> := the <noun-phrase> <verb-phrase>
; <verb-phrase> := <verb> | <verb> <adverb>
; <noun-phrase> := <noun> | <adjective> <noun-phrase>

(define noun-list (list 'dog 'cat 'rat 'professor 'student 'robot))
(define verb-list (list 'ran 'ate 'slept 'drank 'walked 'talked))
(define adjective-list (list 'red 'slow 'annoyed 'happy 'dead))
(define adverb-list (list 'quickly 'happily 'well 'nicely 'grudgingly))

(define (pick-random lst)
  (list-ref lst (random (length lst))))

(define (noun) (pick-random noun-list))
(define (verb) (pick-random verb-list))
(define (adverb) (pick-random adverb-list))
(define (adjective) (pick-random adjective-list))

(define (either a b)
  (if (= (random 2) 0)
      (a)
      (b)))

(define (verb-phrase)
  (either (lambda()(list (verb)))
          (lambda()(list (verb) (adverb)))))

(define (noun-phrase)
  (either (lambda()(list (noun)))
          (lambda()(cons (adjective) (noun-phrase)))))

(define (sentence)
  (append (append (list 'the) (noun-phrase)) (verb-phrase)))

(sentence)
;Value: (the robot ate)
;Value: (the professor slept nicely)
;Value: (the annoyed dead red cat ran)
;Value: (the student talked grudgingly)
;Value: (the professor drank)
;Value: (the slow dog walked)
;Value: (the robot ate well)
;Value: (the happy happy student drank)
;Value: (the slow red slow rat talked nicely)
;Value: (the annoyed happy dog talked grudgingly)

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

; <verb-phrase>              := <verb-intransitive-phrase> 
;                             | <verb-transitive-phrase>
; <verb-intransitive-phrase> := <verb-intransitive> 
;                             | <verb-intransitive> <adverb>
; <verb-transitive-phrase>   := <verb-transitive> <noun-phrase> 
;                             | <verb-transitive> <noun-phrase> <adverb>

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

(define verb-transitive-list (list 'praised 'held 'twisted 'ate))
(define verb-intransitive-list (list 'ate 'ran 'slept 'drank 'fell 'walked 'talked))

(define (verb-transitive) (pick-random verb-transitive-list))
(define (verb-intransitive) (pick-random verb-intransitive-list))

(define (verb-intransitive-phrase)
  (either (lambda()(list (verb-intransitive)))
          (lambda()(list (verb-intransitive) (adverb)))))
(define (verb-transitive-phrase)
  (either (lambda() (cons (verb-transitive) (cons 'the (noun-phrase))))
          (lambda() (append (list (verb-transitive))
                            (cons 'the (noun-phrase))
                            (list (adverb))))))
(define (verb-phrase)
  (either (lambda() (verb-intransitive-phrase))
          (lambda() (verb-transitive-phrase))))

(sentence)
;Value: (the annoyed dog ate the red slow professor happily)
;Value: (the cat ate the dog happily)
;Value: (the annoyed rat twisted the student well)
;Value: (the happy robot praised the rat)
;Value: (the happy professor ate the annoyed professor well)
;Value: (the red happy happy rat twisted the dead dead dog nicely)

------------------------------------------------------
Binary Trees
From Section 2.3.3 of textbook:

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right) (list entry left right))

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

(define (add-to-tree x tree)
  (cond ((null? tree) (make-tree x '() '()))
        ((= x (entry tree)) tree)
        ((< x (entry tree))
         (make-tree (entry tree) 
                    (add-to-tree x (left-branch tree))
                    (right-branch tree)))
        ((> x (entry tree))
         (make-tree (entry tree)
                    (left-branch tree)
                    (add-to-tree x (right-branch tree))))))

(define (make-tree-from-list lst) 
  (if (null? lst) lst
      (add-to-tree (car lst) (make-tree-from-list (cdr lst)))))

(define foo (make-tree-from-list '(1 3 2 5 7 6 4))) 
foo -> (4 (2 (1 #f #f) (3 #f #f)) (6 (5 #f #f) (7 #f #f)))

(define bar (make-tree-from-list '(1 2 3 4 5 6 7)))
bar -> (7 (6 (5 (4 (3 (2 (1 #f #f) #f) #f) #f) #f) #f) #f)

(define baz (make-tree-from-list '(7 6 5 4 3 2 1)))
baz -> (1 #f (2 #f (3 #f (4 #f (5 #f (6 #f (7 #f #f)))))))

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

(define (element-of-tree? x tree)
  (cond ((null? tree) false)
        ((= x (entry tree)) true)
        ((< x (entry tree))
         (element-of-tree? x (left-branch tree)))
        ((> x (entry tree))
         (element-of-tree? x (right-branch tree)))))

(element-of-tree? 2 foo) -> #t
(element-of-tree? 8 foo) -> #f

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

(define (tree->list tree)
  (if (null? tree)
      '()
      (append (tree->list (left-branch tree))
              (cons (entry tree)
                    (tree->list (right-branch tree))))))

(tree->list foo)  ->  (1 2 3 4 5 6 7)
(tree->list bar)  ->  (1 2 3 4 5 6 7)
(tree->list baz)  ->  (1 2 3 4 5 6 7)

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

* can we use this for sorting?   yes!

* what's the order of growth in space for this sort?
  
  O(n) - n deferred make-tree calls

* what's the order of growth in time for this sort?
  (trick question... )

  in the BEST CASE:   O(n log n) for inputs that result in
                      nicely balanced trees

  in the WORST CASE:  O(n^2) for bar & baz since the tree 
                      is unbalanced.

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