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 binary random-access lists. > module MapSequ ( > MapS, > showMapS, > emptyS, > singleS, > lookupS, > mergeS, > ) where > import Sequ > import Map (showMaybe, (<>), combine) > import MapFork > data MapS m v = SpotS > | TrieS (Maybe v) > (MapS (MapF m) v) > (m (MapS (MapF m) v)) > showMapS :: (forall v.(Int -> v -> ShowS) -> (Int -> m v -> ShowS)) > -> (Int -> w -> ShowS) -> (Int -> MapS m w -> ShowS) > showMapS showm showw d SpotS = showString "SpotS" > showMapS showm showw d (TrieS te tz to) > = showParen (d >= 10) ( > showString "TrieS " . showMaybe showw 10 te > . showChar ' ' . showMapS (showMapF showm) showw 10 tz > . showChar ' ' . showm (showMapS (showMapF showm) showw) 10 to) > emptyS :: MapS m w > emptyS = SpotS > > singleS :: (forall v.m v) > -> (forall v.(k, v) -> m v) > -> ((Sequ k, w) -> MapS m w) > singleS e s (Empty, v) = TrieS (Just v) emptyS e > singleS e s (Zero x, v) = TrieS Nothing > (singleS (emptyF e) (singleF e s) (x, v)) > e > singleS e s (One i x, v) = TrieS Nothing > emptyS > (s (i, singleS (emptyF e) (singleF e s) (x, v))) > > lookupS :: (forall v.k -> m v -> Maybe v) > -> Sequ k -> MapS m w -> Maybe w > lookupS l i SpotS = Nothing > lookupS l Empty (TrieS te tz to) > = te > lookupS l (Zero x) (TrieS te tz to) > = lookupS (lookupF l) x tz > lookupS l (One i x) (TrieS te tz to) > = (l i <> lookupS (lookupF l) x) to > > mergeS :: (forall v.(v -> v -> v) -> (m v -> m v -> m v)) > -> (w -> w -> w) -> (MapS m w -> MapS m w -> MapS m w) > mergeS m c SpotS t' = t' > mergeS m c t SpotS = t > mergeS m c (TrieS te tz to) (TrieS te' tz' to') > = TrieS (combine c te te') > (mergeS (mergeF m) c tz tz') > (m (mergeS (mergeF m) c) to to')