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 variables of type `Incr v'.

> module MapIncr (
>     MapI,
>     showMapI,
>     emptyI,
>     singleI,
>     lookupI,
>     mergeI,
> ) where
> import Term
> import Map (showMaybe, (<>), combine)

> data MapI m v			=  SpotI | TrieI (Maybe v) (m v)

> showMapI			:: (forall v.(Int -> v -> ShowS) -> (Int -> m v -> ShowS))
>				   -> (Int -> w -> ShowS) -> (Int -> MapI m w -> ShowS)
> showMapI showm showw d SpotI	=  showString "SpotI"
> showMapI showm showw d (TrieI tz ts)
>				=  showParen (d >= 10) (
>				       showString "TrieI " . showMaybe showw 10 tz
>				           . showChar ' ' . showm showw 10 ts)

> emptyI			:: MapI m w
> emptyI			=  SpotI

> singleI			:: (forall v.m v) -> (forall v.(k, v) -> m v)
>				   -> ((Incr k, w) -> MapI m w)
> singleI e s (Zero, v)		=  TrieI (Just v) e
> singleI e s (Succ i, v)	=  TrieI Nothing (s (i, v))

> lookupI			:: (forall v.k -> m v -> Maybe v)
>			           -> (Incr k -> MapI m w -> Maybe w)
> lookupI l i SpotI		=  Nothing
> lookupI l Zero (TrieI tz ts)	=  tz
> lookupI l (Succ i) (TrieI tz ts)
>				=  l i ts

> mergeI			:: (forall v.(v -> v -> v) -> (m v -> m v -> m v))
>				   -> ((w -> w -> w)
>				       -> (MapI m w -> MapI m w -> MapI m w))
> mergeI m c SpotI t'		=  t'
> mergeI m c t SpotI		=  t
> mergeI m c (TrieI tz ts)  (TrieI tz' ts')
>				=  TrieI (combine c tz tz') (m c ts ts')