Lesson Plan - 6.001 SP04 - recitation 18

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

(define (list-inserters lst)
  (let ((last (last-pair lst)))
    (list (lambda (x)
	    (set-cdr! lst (cons x (cdr lst)))
	    lst)
	  (lambda (x)
	    (set-cdr! last (cons x nil))
	    (set! last x)
	    lst))))

(define the-list (list 1 3 4))

(let ((ins (list-inserters the-list)))
  ((first ins) 2)
  ((second ins) 5))

the-list
	  
(define (create-node value)
  (create-instance make-node value))

(define (make-node self value)
  (let ((root-part (make-root-object self))
	(children '()))
    (lambda (msg)
      (case msg
	((TYPE) (lambda () (type-extend 'trie-node root-part)))
	((VALUE) (lambda () value))
	((CHILD)
	 (lambda (item)
	   (let ((c (assq item children)))
	     (if c
		 (cadr c)
		 c))))
	((SET-VALUE!) (lambda (nv) (set! value nv) 'set))
	((ADD-CHILD!) 
	 (lambda (item node)
	   (set! children (cons (list item node)
				children))
	   'added))
	((LOOKUP)
	 (lambda (key)
	   (if (null? key)
	       (ask self 'VALUE)
	       (let ((c (ask self 'CHILD (car key))))
		 (if c
		     (ask c 'LOOKUP (cdr key))
		     #f)))))
	((INSERT!)
	 (lambda (key value)
	   (if (null? key)
	       (ask self 'SET-VALUE! value)
	       (let ((c (ask self 'CHILD (car key))))
		 (if c
		     (ask c 'INSERT! (cdr key) value)
		     (let ((newnode (create-node #f)))
		       (ask newnode 'INSERT! (cdr key) value)
		       (ask self 'ADD-CHILD! (car key) newnode)))))))
	(else (get-method msg root-part))))))