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'