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