Denotational Design Experiment

DD.hs

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
module DD where

import Data.Functor.Compose
import Data.Monoid

newtype TMap k v = TM (k -> v)
type Map k v = Compose (TMap k) First v

class IsMap d k v where
  mu :: d k v -> Map k v
  mu' :: Map k v -> d k v

data BalancedTree k v = Empty | Node (BalancedTree k v) (k, v) (BalancedTree k v)

data EfficientMap k v = EM
  { mapDefVal :: v
  , mapTree   :: BalancedTree k v
  }

instance Ord k => IsMap EfficientMap k v where
  mu (EM def Empty) = Compose (TM (\_ -> First (Just def)))
  mu m@(EM _ (Node l (k, v) r)) = Compose (TM (\x ->
    case (x == k, x < k) of
      (True, _) -> First (Just v)
      (_, True) -> undefined
      otherwise -> undefined
      ))
  mu' = undefined