public
Created

  • Download Gist
haskell_generic_trie.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
module KTrie ( contains
, empty
, fullDeepLookup
, insert
, lookup
, null
, remove
, toList
, Trie ) where
import qualified Data.Map as M
import Data.Map ((!))
import Prelude hiding (null, lookup)
import Data.Maybe (fromMaybe)
data Trie a = Trie (M.Map a (Trie a)) deriving Show
empty :: Ord a => Trie a
empty = Trie M.empty
null :: Ord a => Trie a -> Bool
null (Trie m) = M.null m
 
insert :: Ord a => [a] -> Trie a -> Trie a
insert [] t = t
insert (x:xs) (Trie m) = Trie m'
where m' = M.alter t' x m
t' = Just . insert xs . fromMaybe empty
remove :: Ord a => [a] -> Trie a -> Trie a
remove [] t = t
remove (x:xs) (Trie m) = Trie m'
where m' = M.alter t x m
t v = case v of
Nothing -> Nothing
Just t' -> if null t'' then Nothing
else Just t''
where t'' = remove xs t'
 
-- contains certain prefix?
contains :: Ord a => [a] -> Trie a -> Bool
contains [] _ = True
contains (x:xs) (Trie m) = case M.lookup x m of
Just t -> contains xs t
Nothing -> False
-- return subtrie, raise error if not exists that prefix
lookup :: Ord a => [a] -> Trie a -> Trie a
lookup [] t = t
lookup (x:xs) t@(Trie m) = lookup xs $ M.findWithDefault t x m

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.