Trie 3

gistfile1.hs

{-# 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)
      where
        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