Accompanying material for the paper "Generalizing Generalized Tries" by Ralf Hinze, in Journal of Functional Programming, 10(4), pp. 327-351, July 2000. Example calls. > import MapList > import qualified OrdList > import Bintree > import MapBintree > import Perfect > import MapPerfect > import Sequ > import MapSequ %-------------------------------= -------------------------------------------- Strings (`[Char]'). > type MapStr = MapL (OrdList.FM Char) > instance (Show v) => Show (MapStr v) where > showsPrec d t = showMapL OrdList.showFM showsPrec d t > emptyStr :: MapStr w > emptyStr = emptyL > singleStr :: (String, w) -> MapStr w > singleStr = singleL OrdList.empty OrdList.single > lookupStr :: String -> MapStr w -> Maybe w > lookupStr = lookupL OrdList.lookup > insertStr :: (w -> w -> w) -> (String, w) -> (MapStr w -> MapStr w) > insertStr c (i, v) t = mergeStr c (singleStr (i, v)) t > mergeStr :: (w -> w -> w) -> (MapStr w -> MapStr w -> MapStr w) > mergeStr = mergeL OrdList.merge > dict :: [(String, String)] > dict = [ ("ear", "Ohr") > , ("earl", "Graf") > , ("east", "Osten") > , ("easy", "einfach") > , ("eye", "Auge") ] Try `foldr (insertStr (\new old -> new)) emptyStr dict'. %-------------------------------= -------------------------------------------- External search trees (`Bintree String Char'). > type MapBSC = MapB MapStr (OrdList.FM Char) > instance (Show v) => Show (MapBSC v) where > showsPrec d m = showMapB (showMapL OrdList.showFM) OrdList.showFM showsPrec d m > emptyBSC :: MapBSC w > emptyBSC = emptyB > singleBSC :: (Bintree String Char, w) -> MapBSC w > singleBSC = singleB emptyStr OrdList.empty singleStr OrdList.single > lookupBSC :: Bintree String Char -> MapBSC w -> Maybe w > lookupBSC = lookupB lookupStr OrdList.lookup > insertBSC :: (w -> w -> w) -> (Bintree String Char, w) -> (MapBSC w -> MapBSC w) > insertBSC c (i, v) t = mergeBSC c (singleBSC (i, v)) t > mergeBSC :: (w -> w -> w) -> (MapBSC w -> MapBSC w -> MapBSC w) > mergeBSC = mergeB mergeStr OrdList.merge > trees :: [(Bintree String Char, Int)] > trees = [ (Leaf "a", 1) > , (Node (Leaf "a") '+' (Leaf "b"), 3) > , (Node (Leaf "a") '+' (Node (Leaf "b") '*' (Leaf "c")), 5) ] Try `foldr (insertBSC (\new old -> new)) emptyBSC trees'. %-------------------------------= -------------------------------------------- Perfectly balanced, binary leaf trees (`Perfect Int'). > type MapPI = MapP (OrdList.FM Int) > instance (Show v) => Show (MapPI v) where > showsPrec d t = showMapP OrdList.showFM showsPrec d t > emptyPI :: MapPI w > emptyPI = emptyP > singlePI :: (Perfect Int, w) -> MapPI w > singlePI = singleP OrdList.empty OrdList.single > lookupPI :: Perfect Int -> MapPI w -> Maybe w > lookupPI = lookupP OrdList.lookup > insertPI :: (w -> w -> w) -> (Perfect Int, w) -> (MapPI w -> MapPI w) > insertPI c (i, v) t = mergePI c (singlePI (i, v)) t > mergePI :: (w -> w -> w) -> (MapPI w -> MapPI w -> MapPI w) > mergePI = mergeP OrdList.merge > perfects :: [(Perfect Int, Int)] > perfects = [ (perfect [0 .. 2^n -1], n) | n <- [0 .. 3] ] Try `foldr (insertBSC (\new old -> new)) emptyBSC trees'. %-------------------------------= -------------------------------------------- Binary random-access lists (`Sequ Char'). > type MapSC = MapS (OrdList.FM Char) > instance (Show v) => Show (MapSC v) where > showsPrec d t = showMapS OrdList.showFM showsPrec d t > emptySC :: MapSC w > emptySC = emptyS > singleSC :: (Sequ Char, w) -> MapSC w > singleSC = singleS OrdList.empty OrdList.single > lookupSC :: Sequ Char -> MapSC w -> Maybe w > lookupSC = lookupS OrdList.lookup > insertSC :: (w -> w -> w) -> (Sequ Char, w) -> (MapSC w -> MapSC w) > insertSC c (i, v) t = mergeSC c (singleSC (i, v)) t > mergeSC :: (w -> w -> w) -> (MapSC w -> MapSC w -> MapSC w) > mergeSC = mergeS OrdList.merge > sdict :: [(Sequ Char, String)] > sdict = [ (sequ s, t) | (s, t) <- dict ] Try `foldr (insertSC (\new old -> new)) emptySC sdict'.