recitation 10: symbols

------------------------------------------------------
* 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

------------------------------------------------------
Evaluation - give printed value (or unspecified, error, or 
procedure where appropriate).  Assume x is bound to 5.

'3  => 3

'x  => 3

''x  => (quote x)

(quote (3 4))  => (3 4)

('+ 3 4)  => ERROR, the symbol + is not applicable

(if '(= x 0) 7 8)  => 7 

(eq? 'x 'X)  => #t 

(eq? (list 1 2) (list 1 2))  => #f 

(equal? (list 1 2) (list 1 2))  => #t 

(quote 1 2 3)  => ERROR, incorrect number of subexpressions to quote

(quote (list (list 1 2)))  => (list (list 1 2))

(list (quote (list 1 2)))  => ((list 1 2))

(car (quote (list)))  => list

(cadr '(+ (* 1 2) (/ 8 4)))  => (* 1 2)

(map car (list '(3) '(4) '(5)))  => (3 4 5)

(filter pair? '(a (b c d) e (f) (g h)))  => ((b c d) (f) (g h))

(cons 'a '(b c d))  => (a b c d)

(append 'a '(b c d))  => ERROR, both args to append should be lists

(quote '(b c d))  => (b c d)

(cons 'a '(b))  => (a b)

(cons '(a) '(b))  => ((a) b)

(list 'a 'b)  => (a b)

(list '(a) '(b))  => ((a) (b))

(append '(a) '(b))  => (a b)

(car ''a) => quote 

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

eq?     returns true if the two things _are_ the same
        (don't use with strings or numbers)

equal?  returns true if the two things print out the same

------------------------------------------------------
Write (member elt lst) that returns #f if elt is not in the list and
returns the tail of the list starting with the first occurence of the
element otherwise.  elt might be a list!

(member '(apple pear) '(x (apple sauce) y apple pear))
   => #f

(member '(apple sauce) '(x (apple sauce) y apple pear))
   => ((apple sauce) y apple pear)

(define (member elt lst)
  (cond ((null? lst) #f)
	((equal? elt (car lst)) lst)
	(else (member elt (cdr lst)))))

------------------------------------------------------
Write (occurrences elt lst) that returns the number of times elt
appears in the list.   elt might be a list!

(define (occurrences elt lst)
  (let ((tmp (member elt lst)))
    (if (null? tmp)
	0
	(+ 1 (occurrences elt (cdr tmp))))))

(occurrences 'b '(a b c d a b c d)) => 2

(occurrences 'e '(a b c d a b c d)) => 0

------------------------------------------------------
A tree is a list of lists.  Write (tree-occurrences sym tree) that
returns the number of times the symbol sym appears in the tree.

(define (tree-occurrences sym tree)
  (cond ((null? tree) 0)
	((pair? tree) (+ (tree-occurrences sym (car tree))
			 (tree-occurrences sym (cdr tree))))
	((eq? sym tree) 1)
	(else 0)))

(tree-occurrences 'a '((a b c) (d e f) (a b a))) => 3

(tree-occurrences 'a '((a b c))) => 1

(tree-occurrences 'd '((a b c))) => 0

------------------------------------------------------
Using eq? write the function tree-equal? that takes two trees of
symbols and returns true if the same symbols are arranged in the same
structure.
 
(tree-equal? '(this is a list) '(this is a list))
;Value: #t

(tree-equal? '(this (is a) list) '(this (is a) list))
;Value: #t

(tree-equal? '(this is a list) '(this (is a) list))
;Value: #f

(define (tree-equal? tree1 tree2)
  (cond ((and (null? tree1) (null? tree2)) #t)
	((and (symbol? tree1) (symbol? tree2)) (eq? tree1 tree2))
	((and (pair? tree1) (pair? tree2))
	 (and (tree-equal? (car tree1) (car tree2))
	      (tree-equal? (cdr tree1) (cdr tree2))))
	(else #f)))
 
------------------------------------------------------