{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"