{-+
A class for finite maps that allows different implementations to impose
different constraints (e.g. Eq or Ord) on the domain type.
-}

module FiniteMaps2 where

class FiniteMap fm d | fm->d where
  empty :: r -> fm r
  lookup :: fm r -> d -> r
  update :: d -> r -> fm r -> fm r

{-+
Example 1: functions as finite maps:
-}
instance Eq d => FiniteMap ((->) d) d where
  empty r = const r
  lookup = id
  update d r fm d' = if d'==d then r else fm d'


{-+
Example 2: binary search trees as finite maps:
-}
data Tree a = Tip | Node a (Tree a) (Tree a)

data FM d r = FM r (Tree (d,r))

instance Ord d => FiniteMap (FM d) d where
  empty r = FM r Tip
  lookup (FM rdefault t) d = look t
    where
      look Tip = rdefault
      look (Node (d',r') l r) =
        case compare d d' of
          EQ -> r'
	  LT -> look l
	  GT -> look r
  update d r (FM rdefault t) = FM rdefault (upd t)
    where
      upd Tip = Node (d,r) Tip Tip
      upd (Node n@(d',r') lt rt) =
        case compare d d' of
          EQ -> Node (d,r) lt rt
	  LT -> Node n (upd lt) rt
	  GT -> Node n lt (upd rt)