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