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