Skip to content

Instantly share code, notes, and snippets.

@kazu-yamamoto
Created October 30, 2012 01:16
Embed
What would you like to do?
Trie 1
import Data.Map (Map)
import qualified Data.Map as M
import Data.Maybe
data Trie k v = Trie (Maybe v) (Map k (Trie k v)) deriving Show
empty :: Trie k v
empty = Trie Nothing M.empty
look :: Ord k => [k] -> Trie k v -> Maybe v
look [] (Trie b _) = b
look (k:ks) (Trie _ m) = M.lookup k m >>= look ks
bind :: Ord k => [k] -> v -> Trie k v -> Trie k v
bind [] x (Trie _ m) = Trie (Just x) m
bind (k:ks) x (Trie b m) = Trie b (M.insert k t' m)
where
t = fromMaybe empty $ M.lookup k m
t' = bind ks x t
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment