okasaki

Okasaki's Purely Functional Data Structures
git clone git://git.jtobin.io/okasaki.git
Log | Files | Refs | LICENSE

Map.hs (923B)

      1 {-# OPTIONS_GHC -Wall -fno-warn-unused-top-binds #-}
      2 {-# LANGUAGE TemplateHaskell #-}
      3 
      4 module Okasaki.Map (
      5     Map(..)
      6   ) where
      7 
      8 import qualified Okasaki.Tree as T
      9 
     10 data Per a b = Per !a b
     11 
     12 instance (Show a, Show b) => Show (Per a b) where
     13   show (Per a b) = show (a, b)
     14 
     15 instance Eq a => Eq (Per a b) where
     16   Per a _ == Per c _ = a == c
     17 
     18 instance Ord a => Ord (Per a b) where
     19   compare (Per a _) (Per b _) = compare a b
     20 
     21 -- exercise 2.6 (use tree to implement a finite map)
     22 newtype Map k a = Map (T.Tree (Per k a))
     23   deriving Show
     24 
     25 non :: Map k a
     26 non = Map T.lef
     27 
     28 -- NB does not replace elements
     29 put :: (Ord k, Eq a) => k -> a -> Map k a -> Map k a
     30 put k a (Map m) = Map $
     31   let per = Per k a
     32   in  T.rub per m
     33 
     34 get :: Ord k => k -> Map k a -> Maybe a
     35 get k (Map m) = do
     36   las <- T.spy (Per k undefined) m -- NB we only care about keys
     37   case las of
     38     Per s v
     39       | s == k    -> pure v
     40       | otherwise -> Nothing
     41