{Record MAP SET} Where Let (MAP compare item_key) (make compare item_key) Let SET Let (item_key item) item In Func compare. Let MAP (make compare item_key) In Let (union set set') (LIST.reduce (MAP.list set) set' MAP.insert) Let (diff set set') (LIST.reduce (MAP.list set) MAP.empty Func set item. Match (MAP.search set' item) | `nothing (MAP.insert set item) | `just._ set ;) In {Record compare empty:MAP.empty new:MAP.new search:MAP.search insert:MAP.insert list:MAP.list union diff } Where Let (make compare item_key) Define (insert depth node item) Cond | (depth = 1) Match node | `one.item' Match (compare (item_key item) (item_key item')) | `less `no_split.`two.{item item'} | `greater `no_split.`two.{item' item} | `equal `no_split.`one.item ; | `two.{item'1 item'2} Let key (item_key item) Let key'1 (item_key item'1) Let key'2 (item_key item'2) In Match (compare key key'1) | `less `split.{`one.item item'1 `one.item'2} | `greater Match (compare key key'2) | `less `split.{`one.item'1 item `one.item'2} | `greater `split.{`one.item'1 item'2 `one.item} | `equal `no_split.`two.{item'1 item} ; | `equal `no_split.`two.{item item'2} ; ; | True Match node | `one.{node'1 item' node'2} Match (compare (item_key item) (item_key item')) | `less Match (insert (depth - 1) node'1 item) | `no_split.node'' `no_split.`one.{node'' item' node'2} | `split.{node''1 item'' node''2} `no_split.`two.{node''1 item'' node''2 item' node'2} ; | `greater Match (insert (depth - 1) node'2 item) | `no_split.node'' `no_split.`one.{node'1 item' node''} | `split.{node''1 item'' node''2} `no_split.`two.{node'1 item' node''1 item'' node''2} ; | `equal `no_split.`one.{node'1 item node'2} ; | `two.{node'1 item'1 node'2 item'2 node'3} Let key (item_key item) Let key'1 (item_key item'1) Let key'2 (item_key item'2) In Match (compare key key'1) | `less Match (insert (depth - 1) node'1 item) | `no_split.node'' `no_split.`two.{node'' item'1 node'2 item'2 node'3} | `split.{node''1 item'' node''2} `split.{ `one.{node''1 item'' node''2} item'1 `one.{node'2 item'2 node'3} } ; | `greater Match (compare key key'2) | `less Match (insert (depth - 1) node'2 item) | `no_split.node'' `no_split.`two.{node'1 item'1 node'' item'2 node'3} | `split.{node''1 item'' node''2} `split.{ `one.{node'1 item'1 node''1} item'' `one.{node''2 item'2 node'3} } ; | `greater Match (insert (depth - 1) node'3 item) | `no_split.node'' `no_split.`two.{node'1 item'1 node'2 item'2 node''} | `split.{node''1 item'' node''2} `split.{ `one.{node'1 item'1 node'2} item'2 `one.{node''1 item'' node''2} } ; | `equal `no_split.`two.{node'1 item'1 node'2 item node'3} ; | `equal `no_split.`two.{node'1 item node'2 item'2 node'3} ; ; ; Let (search tree key) Iterate {depth node} From {tree.depth tree.root} Cond | (depth = 0) `nothing | (depth = 1) Match node | `one.item Match (compare key (item_key item)) | `equal `just.item | _ `nothing ; | `two.{item1 item2} Match (compare key (item_key item1)) | `equal `just.item1 | _ Match (compare key (item_key item2)) | `equal `just.item2 | _ `nothing ; ; ; | True Match node | `one.{node1 item node2} Match (compare key (item_key item)) | `less Continue {(depth - 1) node1} | `equal `just.item | `greater Continue {(depth - 1) node2} ; | `two.{node1 item1 node2 item2 node3} Match (compare key (item_key item1)) | `less Continue {(depth - 1) node1} | `equal `just.item1 | `greater Match (compare key (item_key item2)) | `less Continue {(depth - 1) node2} | `equal `just.item2 | `greater Continue {(depth - 1) node3} ; ; ; ; In Let empty {Record depth:0 root:`zero} Let (insert tree item) If (tree.depth = 0) {Record depth:1 root:`one.item} Match (insert tree.depth tree.root item) | `no_split.node {Record depth:tree.depth root:node} | `split.{node1 item node2} {Record depth:(tree.depth + 1) root:`one.{node1 item node2}} ; Let (list tree) Define (collect depth node list) If (depth = 1) Match node | `one.item (item :: list) | `two.{item1 item2} (item1 :: (item2 :: list)) ; Match node | `one.{node1 item node2} Let depth' (depth - 1) In (collect depth' node1 (item :: (collect depth' node2 list))) | `two.{node1 item1 node2 item2 node3} Let depth' (depth - 1) In Let list (collect depth' node2 (item2 :: (collect depth' node3 list))) In (collect depth' node1 (item1 :: list)) ; In If (tree.depth = 0) [] (collect tree.depth tree.root []) In Let (new items) (LIST.reduce items empty insert) In {Record compare item_key new empty insert search list } Where Let STDIO Package "stdio" Let LIST Package "list"