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 non-closed de Bruijn terms of type `Term Int'.

> import Term
> import MapTerm
> import qualified OrdList

> type MapTI			=  MapT (OrdList.FM Int)

> instance (Show v) => Show (MapTI v) where
>     showsPrec d t		=  showMapT OrdList.showFM showsPrec d t

> emptyTI			:: MapTI w
> emptyTI			=  emptyT

> singleTI			:: (Term Int, w) -> MapTI w
> singleTI			=  singleT OrdList.empty OrdList.single

> lookupTI			:: Term Int -> MapTI w -> Maybe w
> lookupTI			=  lookupT OrdList.lookup

> insertTI			:: (w -> w -> w) -> (Term Int, w) -> (MapTI w -> MapTI w)
> insertTI c (i, v) t		=  mergeTI c (singleTI (i, v)) t

> mergeTI			:: (w -> w -> w) -> (MapTI w -> MapTI w -> MapTI w)
> mergeTI			=  mergeT OrdList.merge

> terms				:: [(Term Int, String)]
> terms				=  [ (Lam (Var Zero), "id")
>				   , (Lam (Lam (Var (Succ Zero))), "fst")
>				   , (Lam (Lam (Var Zero)), "snd") ]

Try `foldr (insertTI (\new old -> new)) emptyTI terms'.