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')