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'