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