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 perfectly balanced, binary leaf trees.

> module MapPerfect (
>     MapP,
>     showMapP,
>     emptyP,
>     singleP,
>     lookupP,
>     mergeP,
> ) where
> import Perfect
> import Map (showMaybe, (<>), combine)
> import MapFork

> data MapP m v			=  SpotP
>				|  TrieP (m v)
>				         (MapP (MapF m) v)

> showMapP			:: (forall v.(Int -> v -> ShowS) -> (Int -> m v -> ShowS))
>				   -> (Int -> w -> ShowS) -> (Int -> MapP m w -> ShowS)
> showMapP showm showw d SpotP	=  showString "SpotP"
> showMapP showm showw d (TrieP tn ts)
>				=  showParen (d >= 10) (
>				       showString "TrieP " . showm showw 10 tn
>				       . showChar ' ' . showMapP (showMapF showm) showw 10 ts)

> emptyP			:: MapP m w
> emptyP			=  SpotP

> singleP			:: (forall v.m v) -> (forall v.(k, v) -> m v)
>				   -> ((Perfect k, w) -> MapP m w)
> singleP e s (Null i, v)	=  TrieP (s (i, v)) emptyP
> singleP e s (Succ i, v)	=  TrieP e (singleP (emptyF e) (singleF e s) (i, v))

> lookupP			:: (forall v.k -> m v -> Maybe v)
>				   -> (Perfect k -> MapP m w -> Maybe w)
> lookupP l i SpotP		=  Nothing
> lookupP l (Null i) (TrieP tn ts)
>				=  l i tn
> lookupP l (Succ i) (TrieP tn ts)
>				=  lookupP (lookupF l) i ts 

> mergeP			:: (forall v.(v -> v -> v) -> (m v -> m v -> m v))
>				   -> ((w -> w -> w) -> (MapP m w -> MapP m w -> MapP m w))
> mergeP m c SpotP t'		=  t'
> mergeP m c t SpotP		=  t
> mergeP m c (TrieP tn ts) (TrieP tn' ts')
> 				=  TrieP (m c tn tn') (mergeP (mergeF m) c ts ts')