Recitation 9
HOPs, programming methods

Solutions

(define (make-node val left right)
  (lambda (p)
    (p val left right)))

(define (get-val node)
  (node (lambda (val left right) val)))

(define (get-left node)
  (node (lambda (val left right) left)))

(define (get-right node)
  (node (lambda (val left right) right)))

(define (node->list node)
  (node (lambda (val left right)
	  (list val
		(if left (node->list left) left)
		(if right (node->list right) right)))))

(define (new-right node right)
  (node (lambda (val left oldright) (lambda (p) (p val left right)))))

(define (new-left node left)
  (node (lambda (val oldleft right) (lambda (p) (p val left right)))))

(define (leaf? node)
  (node (lambda (val left right) (and (not left) (not right)))))

(define (insert-tree val tree)
  (cond ((not tree)
	 (make-node val #f #f))
	((< val (get-val tree))
	 (new-left tree (insert-tree val (get-left tree))))
	(else
	 (new-right tree (insert-tree val (get-right tree))))))

(define (in-order-read tree)
  (cond ((not tree)
	 nil)
	(else
	 (append (in-order-read (get-left tree))
		 (list (get-val tree))
		 (in-order-read (get-right tree))))))


(define (mysort lst)
  (in-order-read (fold-right insert-tree #f lst)))