module type BST = sig type 'a tree (* abstract tree type *) val create : 'a tree val insert : 'a tree -> 'a -> 'a tree val contains : 'a tree -> 'a -> bool val map : ('a -> 'a) -> 'a tree -> 'a tree val fold : ('b -> 'a -> 'b) -> 'b -> 'a tree -> 'b end module BSTImpl = struct (* define tree type consisting of inner nodes and leaf nodes *) type 'a tree = Node of ('a * 'a tree * 'a tree) | Leaf (* create an empty tree *) let create = Leaf ;; (* create new tree by inserting v into n *) let rec insert n v = match n with | Leaf -> Node (v, Leaf, Leaf) | Node (x, left, right) -> if x < v then Node (x, (insert left v), right) else if x > v then Node (x, left, (insert right v)) else n ;; (* return true if n contains v *) let rec contains n v = match n with | Leaf -> false | Node (x, left, right) -> if x < v then contains left v else if x > v then contains right v else true ;; (* create new tree by applying f to the values of n *) let rec map f n = match n with | Leaf -> Leaf | Node (x, left, right) -> Node ((f x), (map f left), (map f right)) ;; (* perform fold operation by in-order traversal of n *) let rec fold f a n = match n with | Leaf -> a | Node (x, left, right) -> fold f (f (fold f a left) x) right ;; end module Bst : BST = BSTImpl;; let tree = Bst.create;; let tree = Bst.insert tree 50;; let tree = Bst.insert tree 25;; let tree = Bst.insert tree 75;; let tree = Bst.insert tree 0;; let tree = Bst.insert tree 100;; let tree = Bst.insert tree 40;; let tree = Bst.insert tree 60;; let tree = Bst.map (fun x -> x * 2) tree;; Bst.fold (fun a x -> x::a) [] tree;;