Skip to content

Instantly share code, notes, and snippets.

Created October 30, 2012 01:20
What would you like to do?
Trie 3
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}
import Data.Map (Map)
import qualified Data.Map as M
import Data.Maybe
data Trie m ks v = Trie (Maybe v) (m (Trie m ks v))
class FiniteMap m k where
empty :: m k v
look :: k -> m k v -> Maybe v
bind :: k -> v -> m k v -> m k v
instance FiniteMap m k => FiniteMap (Trie (m k)) [k] where
empty = Trie Nothing empty
look [] (Trie b _) = b
look (k:ks) (Trie _ m) = look k m >>= look ks
bind [] x (Trie _ m) = Trie (Just x) m
bind (k:ks) x (Trie b m) = Trie b (bind k t' m)
t = fromMaybe empty $ look k m
t' = bind ks x t
instance FiniteMap Map Char where
empty = M.empty
look = M.lookup
bind = M.insert
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment