%-------------------------------=  --------------------------------------------
\subsection{Finite maps}
%-------------------------------=  --------------------------------------------

%if codeOnly || showModuleHeader

> module FiniteMap              (  FiniteMap, empty, fromList, add, lookup, (!), keys)
> where
> import Prelude hiding         (  lookup  )
> import Data.Maybe

%endif

> type FiniteMap key val        =  Trie key val
>
> data Trie key val             =  Leaf [key] val
>                               |  Node [(key, Trie key val)] (Maybe val)

The value associated with the empty sequence is contained in the |Maybe b|
part. \NB |Node [('a', empty)] Nothing| is not legal.

> empty                         :: Trie key val
> empty                         =  Node [] Nothing
>
> fromList                      :: (Ord key) => [([key], val)] -> Trie key val
> fromList                      =  foldr add empty
>
> add                           :: (Ord a) => ([a], b) -> Trie a b -> Trie a b
> add (x, v) t                  =  insert t x v
>
> lookup                        :: (Ord a) => [a] -> Trie a b -> Maybe b
> lookup x (Leaf y w)
>     | x == y                  =  Just w
>     | otherwise               =  Nothing
> lookup [] (Node ts w)         =  w
> lookup (a : x) (Node ts w)    =  lookupList ts
>     where
>     lookupList []             =  Nothing
>     lookupList ((b, t) : ts)  =  case compare b a of
>         LT                    -> lookupList ts
>         EQ                    -> lookup x t
>         GT                    -> Nothing

> keys                          :: (Ord a) => Trie a b -> [[a]]
> keys                          =  keys' []
>     where
>     keys' acc (Leaf x _)      =  [acc ++ x]
>     keys' acc (Node xs v)     =  maybe [] (const [acc]) v ++
>                                  concatMap (\ (x,t) -> keys' (acc ++ [x]) t) xs

Derived functions.

> (!)                           :: (Ord a) => Trie a b -> [a] -> b
> t ! k                         =  fromJust (lookup k t)

Auxiliary functions.
%{
%align 41

> insert                                :: (Ord a) => Trie a b -> [a] -> b -> Trie a b
> insert (Leaf [] _) [] v               =  Leaf [] v
> insert (Leaf (b : y) w) [] v          =  Node [(b, Leaf y w)] (Just v)
> insert (Leaf [] w) (a : x) v          =  Node [(a, Leaf x v)] (Just w)
> insert (Leaf (b : y) w) (a : x) v     =  case compare b a of
>     LT                                -> Node [(b, Leaf y w), (a, Leaf x v)] Nothing
>     EQ                                -> Node [(a, insert (Leaf y w) x v)] Nothing
>     GT                                -> Node [(a, Leaf x v), (b, Leaf y w)] Nothing
> insert (Node ts w) [] v               =  Node ts (Just v)
> insert (Node ts w) (a : x) v          =  Node (insList ts) w
>     where
>     insList []                        =  [(a,Leaf x v)]
>     insList ((b, t) : ts)             =  case compare b a of
>         LT                            -> (b, t) : insList ts
>         EQ                            -> (b, insert t x v) : ts
>         GT                            -> (a, Leaf x v) : (b, t) : ts

%}