Lesson Plan - 6.001 SP04 - recitation 17

quiz 2 review

solutions (not for environment diagram tho)

(define (compose f g)
  (lambda (x) (f (g x))))
(define (fracture s)
  (map (compose string->symbol char->name) (string->list s)))

(define (make-node value)
  (list 'trie-node value '()))
(define (trie-node? x)
  (and (pair? x) (eq? (car x) 'trie-node)))
(define (node-value node)
  (second node))
(define (node-child item node)
  (let ((c (assq item (third node))))
    (if c
	(cadr c)
	c)))
(define (trie-lookup key node)
  (if (null? key)
      (node-value node)
      (let ((child (node-child (car key) node)))
	(if child
	    (trie-lookup (cdr key) child)
	    #f))))

(define (trie-insert! key value node)
  (if (null? key)
      (set-car! (cdr node) value)
      (let ((child (node-child (car key) node)))
	(if child
	    (trie-insert! (cdr key) value child)
	    (let ((newnode (make-node #f)))
	      (trie-insert! (cdr key) value newnode)
	      (set-car! (cddr node)
			(cons (list (car key)
				    newnode)
			      (third node))))))))

(define trie (make-node #f))
(trie-insert! (fracture "hi") 'yay trie)
(trie-lookup (fracture "hi") trie)       ; yay
(trie-lookup (fracture "h") trie)        ; #f
(trie-insert! (fracture "hum") 'wonderful trie)
(trie-lookup (fracture "hum") trie)      ; wonderful
(pp trie)