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 lists. > module MapList ( > MapL, > showMapL, > emptyL, > singleL, > lookupL, > mergeL, > ) where > import Map (showMaybe, (<>), combine) > data MapL m v = SpotL | TrieL (Maybe v) (m (MapL m v)) > showMapL :: (forall v.(Int -> v -> ShowS) -> (Int -> m v -> ShowS)) > -> (Int -> w -> ShowS) -> (Int -> MapL m w -> ShowS) > showMapL showm showw d SpotL = showString "SpotL" > showMapL showm showw d (TrieL tn tc) > = showParen (d >= 10) ( > showString "TrieL " . showMaybe showw 10 tn > . showChar ' ' . showm (showMapL showm showw) 10 tc) > emptyL :: MapL m w > emptyL = SpotL > singleL :: (forall v.m v) > -> (forall v.(k, v) -> m v) > -> (([k], w) -> MapL m w) > singleL e s ([], v) = TrieL (Just v) e > singleL e s (i : is, v) = TrieL Nothing (s (i, singleL e s (is, v))) > lookupL :: (forall v.k -> m v -> Maybe v) > -> [k] -> MapL m w -> Maybe w > lookupL l is SpotL = Nothing > lookupL l [] (TrieL tn tc) = tn > lookupL l (i : is) (TrieL tn tc) > = (l i <> lookupL l is) tc > mergeL :: (forall v.(v -> v -> v) -> (m v -> m v -> m v)) > -> (w -> w -> w) -> (MapL m w -> MapL m w -> MapL m w) > mergeL m c SpotL m2 = m2 > mergeL m c m1 SpotL = m1 > mergeL m c (TrieL tn tc) (TrieL tn' tc') > = TrieL (combine c tn tn') > (m (mergeL m c) tc tc')