toy-adt.clj

;;;; structural types + pattern matching in Clojure
;;;; with the obligatory unbalanced binary tree example

(define-struct leaf value)
(define-struct node left elt right)

(define insert
  nil      x -> (leaf x)
  (leaf a) x -> (cond (or (nil? a) (= a x)) (leaf a)
                      (< x a) (node (leaf x) a nil)
                      (< a x) (node (leaf a) x nil))
  
  (node a b c) x -> (cond (< x b) (node (insert a x) b c)
                          (= x b) (node a b c)
                          (> x b) (node a b (insert c x))))

(define member?
  nil _          -> false
  (leaf a) x     -> (= a x)
  (node a b c) x -> (cond (< x b) (member? a x)
                          (> x b) (member? c x)
                          :else   true))

(def a (insert nil 42)) => (leaf 42)
(member? a 42)          => true
(def b (insert a 21))   => (node (leaf 21) 42 (leaf nil))
(member? b 21)          => true
(member? b 99)          => false