Accompanying material for the paper "Generalizing Generalized Tries"
by Ralf Hinze, in Journal of Functional Programming, 10(4),
pp. 327-351, July 2000.

Spotted tries for external binary search trees.

> module MapBintree (
>     MapB,
>     showMapB,
>     emptyB,
>     singleB,
>     lookupB,
>     mergeB,
> ) where
> import Bintree
> import Map ((<>), combine)

> data MapB m1 m2 v		=  SpotB
>				|  TrieB (m1 v)
>				         (MapB m1 m2 (m2 (MapB m1 m2 v)))

> showMapB			:: (forall v.(Int -> v -> ShowS) -> (Int -> m1 v -> ShowS))
>				   -> (forall v.(Int -> v -> ShowS) -> (Int -> m2 v -> ShowS))
>				   -> (Int -> w -> ShowS) -> (Int -> MapB m1 m2 w -> ShowS)
> showMapB showm1 showm2 showw d SpotB
>				=  showString "SpotB"
> showMapB showm1 showm2 showw d (TrieB tl tn)
>				=  showParen (d >= 10) (
>				       showString "TrieB " . showm1 showw 10 tl
>				       . showChar ' ' . showMapB showm1 showm2
>				                            (showm2
>				                                (showMapB showm1 showm2 showw)) 10 tn)

> emptyB			:: MapB m1 m2 w
> emptyB			=  SpotB

> singleB			:: (forall v.m1 v)
>				   -> (forall v.m2 v)
>				   -> (forall v.(k1, v) -> m1 v)
>				   -> (forall v.(k2, v) -> m2 v)
>				   -> ((Bintree k1 k2, w) -> MapB m1 m2 w)
> singleB e1 e2 s1 s2 (Leaf i, v)
>				=  TrieB (s1 (i, v)) emptyB
> singleB e1 e2 s1 s2 (Node il i ir, v)
>				=  TrieB e1 (singleB e1 e2 s1 s2 (il,
>				              (s2 (i,
>				                (singleB e1 e2 s1 s2 (ir, v))))))

> lookupB			:: (forall v.k1 -> m1 v -> Maybe v)
>				   -> (forall v.k2 -> m2 v -> Maybe v)
>				   -> Bintree k1 k2 -> MapB m1 m2 w -> Maybe w
> lookupB l1 l2 it SpotB	=  Nothing
> lookupB l1 l2 (Leaf i) (TrieB tl tn)
>				=  l1 i tl
> lookupB l1 l2 (Node il i ir) (TrieB tl tn)
>				=  (lookupB l1 l2 il <> l2 i <> lookupB l1 l2 ir) tn

> mergeB			:: (forall v.(v -> v -> v) -> (m1 v -> m1 v -> m1 v))
>				   -> (forall v.(v -> v -> v) -> (m2 v -> m2 v -> m2 v))
>				   -> (w -> w -> w) -> (MapB m1 m2 w -> MapB m1 m2 w -> MapB m1 m2 w)
> mergeB m1 m2 c SpotB t2	=  t2
> mergeB m1 m2 c t1 SpotB	=  t1
> mergeB m1 m2 c (TrieB tl tn) (TrieB tl' tn')
> 				=  TrieB (m1 c tl tl')
>				         (mergeB m1 m2 (m2 (mergeB m1 m2 c)) tn tn')