Accompanying material for the paper "Generalizing Generalized Tries"
by Ralf Hinze, in Journal of Functional Programming, 10(4),
pp. 327-351, July 2000.

Finite maps based on ordered association lists.

> module OrdList (
>     FM,
>     showFM,
>     empty,
>     single,
>     lookup,
>     insert,
>     merge,
> ) where
> import Prelude hiding (lookup)

> data FM k v			=  FM [(k, v)]

> assocs			:: FM k v -> [(k, v)]
> assocs (FM xs)		=  xs

> showFM			:: (Show k) => (Int -> w -> ShowS) -> (Int -> FM k w -> ShowS)
> showFM showw d (FM [])	=  showString "[]"
> showFM showw d (FM (x : xs))	=  showChar '[' . showp x . showl xs
>     where
>     showl []			=  showChar ']'
>     showl (y : ys)		=  showChar ',' . showp y . showl ys
>     showp (i, v)		=  showChar '(' . shows i . showChar ','
>				       . showw 0 v . showChar ')'

> empty				:: FM k v
> empty				=  FM []

> single			:: (k, v) -> FM k v
> single (i, v)			=  FM [(i, v)]

> lookup			:: (Ord k) => k -> FM k v -> Maybe v
> lookup i m			=  lookup' (assocs m)
>   where
>   lookup' []			=  Nothing
>   lookup' ((i', v) : xs)	=  case compare i i' of
>				       LT -> Nothing
>				       EQ -> Just v
>				       GT -> lookup' xs

> insert			:: (Ord k) => (v -> v -> v) -> (k, v) -> (FM k v -> FM k v)
> insert c (i, v) m		=  merge c (single (i, v)) m

> merge				:: (Ord k) => (v -> v -> v) -> (FM k v -> FM k v -> FM k v)
> merge c m1 m2			=  FM (merge' (assocs m1) (assocs m2))
>   where
>   merge' [] ys		=  ys
>   merge' xs []		=  xs
>   merge' xs@((i, v) : xs') ys@((j, w) : ys')
>				=  case compare i j of
>				       LT -> (i, v)     : merge' xs' ys
>				       EQ -> (i, c v w) : merge' xs' ys'
>				       GT -> (j, w)     : merge' xs  ys'