This is the code from the paper "Generalizing Generalized Tries" by
Ralf Hinze, in Journal of Functional Programming, 10(4), pp. 327-351,
July 2000.

%-------------------------------=  --------------------------------------------
1. Introduction
%-------------------------------=  --------------------------------------------

Finite map implementation for characters (using a simple association
list).

> type MapChar v		=  [(Char, v)]
>
> lookupChar			:: Char -> MapChar v -> v
> lookupChar c []		=  error "not found"
> lookupChar c ((c', v) : x)	=  if c == c' then v else lookupChar c x

Strings.

> data Str			=  Nil | Cons Char Str

Tries for strings (NB `Maybe' is predefined in Haskell).

> data MapStr v			=  TrieStr (Maybe v) (MapChar (MapStr v))

> lookupStr			:: Str -> MapStr v -> v
> lookupStr Nil (TrieStr tn tc)	=  value tn
> lookupStr (Cons c s) (TrieStr tn tc)
>				=  (lookupStr s . lookupChar c) tc
>
> value				:: Maybe v -> v
> value Nothing			=  error "not found"
> value (Just v)		=  v

External search trees.

> data Bin			=  Leaf Str | Node Bin Char Bin

Tries for external search trees.

> data MapBin v			=  TrieBin (MapStr v)
>				           (MapBin (MapChar (MapBin v)))

> lookupBin			:: Bin -> MapBin v -> v
> lookupBin (Leaf s) (TrieBin tl tn)
>				=  lookupStr s tl
> lookupBin (Node l c r) (TrieBin tl tn)
>				=  (lookupBin r . lookupChar c . lookupBin l) tn

Tries for strings employing reverse textual order.

> data MapStrR v		=  TrieStrR (Maybe v) (MapStrR (MapChar v))
>
> lookupStrR			:: Str -> MapStrR v -> v
> lookupStrR Nil (TrieStrR tn tc)
>				=  value tn
> lookupStrR (Cons c s) (TrieStrR tn tc)
>				=  (lookupChar c . lookupStrR s) tc