EdisonCore-1.2.1.2: A library of efficent, purely-functional data structures (Core Implementations)Source codeContentsIndex
Data.Edison.Assoc.TernaryTrie
PortabilityGHC, Hugs (MPTC and FD)
Stabilitystable
Maintainerrobdockins AT fastmail DOT fm
Contents
Type of ternary search tries
AssocX operations
Assoc operations
FiniteMapX operations
FiniteMap operations
OrdAssocX operations
OrdAssoc operations
Other supported operations
Documentation
Description
Finite maps implemented as ternary search tries
Synopsis
data FM k a
empty :: Ord k => FM k a
singleton :: Ord k => [k] -> a -> FM k a
fromSeq :: (Ord k, Sequence seq) => seq ([k], a) -> FM k a
insert :: Ord k => [k] -> a -> FM k a -> FM k a
insertSeq :: (Ord k, Sequence seq) => seq ([k], a) -> FM k a -> FM k a
union :: Ord k => FM k a -> FM k a -> FM k a
unionSeq :: (Ord k, Sequence seq) => seq (FM k a) -> FM k a
delete :: Ord k => [k] -> FM k a -> FM k a
deleteAll :: Ord k => [k] -> FM k a -> FM k a
deleteSeq :: (Ord k, Sequence seq) => seq [k] -> FM k a -> FM k a
null :: Ord k => FM k a -> Bool
size :: Ord k => FM k a -> Int
member :: Ord k => [k] -> FM k a -> Bool
count :: Ord k => [k] -> FM k a -> Int
lookup :: Ord k => [k] -> FM k a -> a
lookupM :: (Ord k, Monad rm) => [k] -> FM k a -> rm a
lookupAll :: (Ord k, Sequence seq) => [k] -> FM k a -> seq a
lookupAndDelete :: Ord k => [k] -> FM k a -> (a, FM k a)
lookupAndDeleteM :: (Ord k, Monad rm) => [k] -> FM k a -> rm (a, FM k a)
lookupAndDeleteAll :: (Ord k, Sequence seq) => [k] -> FM k a -> (seq a, FM k a)
lookupWithDefault :: Ord k => a -> [k] -> FM k a -> a
adjust :: Ord k => (a -> a) -> [k] -> FM k a -> FM k a
adjustAll :: Ord k => (a -> a) -> [k] -> FM k a -> FM k a
adjustOrInsert :: Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k a
adjustAllOrInsert :: Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k a
adjustOrDelete :: Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k a
adjustOrDeleteAll :: Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k a
strict :: FM k a -> FM k a
strictWith :: (a -> b) -> FM k a -> FM k a
map :: Ord k => (a -> b) -> FM k a -> FM k b
fold :: Ord k => (a -> b -> b) -> b -> FM k a -> b
fold' :: Ord k => (a -> b -> b) -> b -> FM k a -> b
fold1 :: Ord k => (a -> a -> a) -> FM k a -> a
fold1' :: Ord k => (a -> a -> a) -> FM k a -> a
filter :: Ord k => (a -> Bool) -> FM k a -> FM k a
partition :: Ord k => (a -> Bool) -> FM k a -> (FM k a, FM k a)
elements :: (Ord k, Sequence seq) => FM k a -> seq a
structuralInvariant :: Ord k => FM k a -> Bool
toSeq :: (Ord k, Sequence seq) => FM k a -> seq ([k], a)
keys :: (Ord k, Sequence seq) => FM k a -> seq [k]
mapWithKey :: Ord k => ([k] -> a -> b) -> FM k a -> FM k b
foldWithKey :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldWithKey' :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
filterWithKey :: Ord k => ([k] -> a -> Bool) -> FM k a -> FM k a
partitionWithKey :: Ord k => ([k] -> a -> Bool) -> FM k a -> (FM k a, FM k a)
fromSeqWith :: (Ord k, Sequence seq) => (a -> a -> a) -> seq ([k], a) -> FM k a
fromSeqWithKey :: (Ord k, Sequence seq) => ([k] -> a -> a -> a) -> seq ([k], a) -> FM k a
insertWith :: Ord k => (a -> a -> a) -> [k] -> a -> FM k a -> FM k a
insertWithKey :: Ord k => ([k] -> a -> a -> a) -> [k] -> a -> FM k a -> FM k a
insertSeqWith :: (Ord k, Sequence seq) => (a -> a -> a) -> seq ([k], a) -> FM k a -> FM k a
insertSeqWithKey :: (Ord k, Sequence seq) => ([k] -> a -> a -> a) -> seq ([k], a) -> FM k a -> FM k a
unionl :: Ord k => FM k a -> FM k a -> FM k a
unionr :: Ord k => FM k a -> FM k a -> FM k a
unionWith :: Ord k => (a -> a -> a) -> FM k a -> FM k a -> FM k a
unionSeqWith :: (Ord k, Sequence seq) => (a -> a -> a) -> seq (FM k a) -> FM k a
intersectionWith :: Ord k => (a -> b -> c) -> FM k a -> FM k b -> FM k c
difference :: Ord k => FM k a -> FM k b -> FM k a
properSubset :: Ord k => FM k a -> FM k b -> Bool
subset :: Ord k => FM k a -> FM k b -> Bool
properSubmapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
submapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
sameMapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
properSubmap :: (Ord k, Eq a) => FM k a -> FM k a -> Bool
submap :: (Ord k, Eq a) => FM k a -> FM k a -> Bool
sameMap :: (Ord k, Eq a) => FM k a -> FM k a -> Bool
unionWithKey :: Ord k => ([k] -> a -> a -> a) -> FM k a -> FM k a -> FM k a
unionSeqWithKey :: (Ord k, Sequence seq) => ([k] -> a -> a -> a) -> seq (FM k a) -> FM k a
intersectionWithKey :: Ord k => ([k] -> a -> b -> c) -> FM k a -> FM k b -> FM k c
minView :: Monad m => FM k a -> m (a, FM k a)
minElem :: FM t1 t -> t
deleteMin :: Ord k => FM k a -> FM k a
unsafeInsertMin :: Ord k => [k] -> a -> FM k a -> FM k a
maxView :: Monad m => FM k a -> m (a, FM k a)
maxElem :: FM k a -> a
deleteMax :: Ord k => FM k a -> FM k a
unsafeInsertMax :: Ord k => [k] -> a -> FM k a -> FM k a
foldr :: Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr' :: Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr1 :: Ord k => (a -> a -> a) -> FM k a -> a
foldr1' :: Ord k => (a -> a -> a) -> FM k a -> a
foldl :: (a -> b -> a) -> a -> FM t b -> a
foldl' :: (a -> b -> a) -> a -> FM t b -> a
foldl1 :: (b -> b -> b) -> FM k b -> b
foldl1' :: (b -> b -> b) -> FM k b -> b
unsafeFromOrdSeq :: (Ord k, Sequence seq) => seq ([k], a) -> FM k a
unsafeAppend :: Ord k => FM k a -> FM k a -> FM k a
filterLT :: Ord k => [k] -> FM k a -> FM k a
filterLE :: Ord k => [k] -> FM k a -> FM k a
filterGT :: Ord k => [k] -> FM k a -> FM k a
filterGE :: Ord k => [k] -> FM k a -> FM k a
partitionLT_GE :: Ord k => [k] -> FM k a -> (FM k a, FM k a)
partitionLE_GT :: Ord k => [k] -> FM k a -> (FM k a, FM k a)
partitionLT_GT :: Ord k => [k] -> FM k a -> (FM k a, FM k a)
minViewWithKey :: Monad m => FM k a -> m (([k], a), FM k a)
minElemWithKey :: FM k a -> ([k], a)
maxViewWithKey :: Monad m => FM k a -> m (([k], a), FM k a)
maxElemWithKey :: FM k a -> ([k], a)
foldrWithKey :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey' :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldlWithKey :: Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> b
foldlWithKey' :: Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> b
toOrdSeq :: (Ord k, Sequence seq) => FM k a -> seq ([k], a)
mergeVFM :: Ord k => (Maybe a -> Maybe b -> Maybe c) -> FM k a -> FM k b -> FM k c
mergeKVFM :: Ord k => ([k] -> Maybe a -> Maybe b -> Maybe c) -> FM k a -> FM k b -> FM k c
moduleName :: String
Type of ternary search tries
data FM k a Source
show/hide Instances
Ord k => Functor (FM k)
Ord k => AssocX (FM k) ([] k)
Ord k => OrdAssocX (FM k) ([] k)
Ord k => FiniteMapX (FM k) ([] k)
Ord k => OrdFiniteMapX (FM k) ([] k)
Ord k => Assoc (FM k) ([] k)
Ord k => OrdAssoc (FM k) ([] k)
Ord k => FiniteMap (FM k) ([] k)
Ord k => OrdFiniteMap (FM k) ([] k)
(Ord k, Eq a) => Eq (FM k a)
(Ord k, Ord a) => Ord (FM k a)
(Ord k, Read k, Read a) => Read (FM k a)
(Ord k, Show k, Show a) => Show (FM k a)
Ord k => Monoid (FM k a)
(Ord k, Arbitrary k, Arbitrary a) => Arbitrary (FM k a)
AssocX operations
empty :: Ord k => FM k aSource
singleton :: Ord k => [k] -> a -> FM k aSource
fromSeq :: (Ord k, Sequence seq) => seq ([k], a) -> FM k aSource
insert :: Ord k => [k] -> a -> FM k a -> FM k aSource
insertSeq :: (Ord k, Sequence seq) => seq ([k], a) -> FM k a -> FM k aSource
union :: Ord k => FM k a -> FM k a -> FM k aSource
unionSeq :: (Ord k, Sequence seq) => seq (FM k a) -> FM k aSource
delete :: Ord k => [k] -> FM k a -> FM k aSource
deleteAll :: Ord k => [k] -> FM k a -> FM k aSource
deleteSeq :: (Ord k, Sequence seq) => seq [k] -> FM k a -> FM k aSource
null :: Ord k => FM k a -> BoolSource
size :: Ord k => FM k a -> IntSource
member :: Ord k => [k] -> FM k a -> BoolSource
count :: Ord k => [k] -> FM k a -> IntSource
lookup :: Ord k => [k] -> FM k a -> aSource
lookupM :: (Ord k, Monad rm) => [k] -> FM k a -> rm aSource
lookupAll :: (Ord k, Sequence seq) => [k] -> FM k a -> seq aSource
lookupAndDelete :: Ord k => [k] -> FM k a -> (a, FM k a)Source
lookupAndDeleteM :: (Ord k, Monad rm) => [k] -> FM k a -> rm (a, FM k a)Source
lookupAndDeleteAll :: (Ord k, Sequence seq) => [k] -> FM k a -> (seq a, FM k a)Source
lookupWithDefault :: Ord k => a -> [k] -> FM k a -> aSource
adjust :: Ord k => (a -> a) -> [k] -> FM k a -> FM k aSource
adjustAll :: Ord k => (a -> a) -> [k] -> FM k a -> FM k aSource
adjustOrInsert :: Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k aSource
adjustAllOrInsert :: Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k aSource
adjustOrDelete :: Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k aSource
adjustOrDeleteAll :: Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k aSource
strict :: FM k a -> FM k aSource
strictWith :: (a -> b) -> FM k a -> FM k aSource
map :: Ord k => (a -> b) -> FM k a -> FM k bSource
fold :: Ord k => (a -> b -> b) -> b -> FM k a -> bSource
fold' :: Ord k => (a -> b -> b) -> b -> FM k a -> bSource
fold1 :: Ord k => (a -> a -> a) -> FM k a -> aSource
fold1' :: Ord k => (a -> a -> a) -> FM k a -> aSource
filter :: Ord k => (a -> Bool) -> FM k a -> FM k aSource
partition :: Ord k => (a -> Bool) -> FM k a -> (FM k a, FM k a)Source
elements :: (Ord k, Sequence seq) => FM k a -> seq aSource
structuralInvariant :: Ord k => FM k a -> BoolSource
Assoc operations
toSeq :: (Ord k, Sequence seq) => FM k a -> seq ([k], a)Source
keys :: (Ord k, Sequence seq) => FM k a -> seq [k]Source
mapWithKey :: Ord k => ([k] -> a -> b) -> FM k a -> FM k bSource
foldWithKey :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> bSource
foldWithKey' :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> bSource
filterWithKey :: Ord k => ([k] -> a -> Bool) -> FM k a -> FM k aSource
partitionWithKey :: Ord k => ([k] -> a -> Bool) -> FM k a -> (FM k a, FM k a)Source
FiniteMapX operations
fromSeqWith :: (Ord k, Sequence seq) => (a -> a -> a) -> seq ([k], a) -> FM k aSource
fromSeqWithKey :: (Ord k, Sequence seq) => ([k] -> a -> a -> a) -> seq ([k], a) -> FM k aSource
insertWith :: Ord k => (a -> a -> a) -> [k] -> a -> FM k a -> FM k aSource
insertWithKey :: Ord k => ([k] -> a -> a -> a) -> [k] -> a -> FM k a -> FM k aSource
insertSeqWith :: (Ord k, Sequence seq) => (a -> a -> a) -> seq ([k], a) -> FM k a -> FM k aSource
insertSeqWithKey :: (Ord k, Sequence seq) => ([k] -> a -> a -> a) -> seq ([k], a) -> FM k a -> FM k aSource
unionl :: Ord k => FM k a -> FM k a -> FM k aSource
unionr :: Ord k => FM k a -> FM k a -> FM k aSource
unionWith :: Ord k => (a -> a -> a) -> FM k a -> FM k a -> FM k aSource
unionSeqWith :: (Ord k, Sequence seq) => (a -> a -> a) -> seq (FM k a) -> FM k aSource
intersectionWith :: Ord k => (a -> b -> c) -> FM k a -> FM k b -> FM k cSource
difference :: Ord k => FM k a -> FM k b -> FM k aSource
properSubset :: Ord k => FM k a -> FM k b -> BoolSource
subset :: Ord k => FM k a -> FM k b -> BoolSource
properSubmapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> BoolSource
submapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> BoolSource
sameMapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> BoolSource
properSubmap :: (Ord k, Eq a) => FM k a -> FM k a -> BoolSource
submap :: (Ord k, Eq a) => FM k a -> FM k a -> BoolSource
sameMap :: (Ord k, Eq a) => FM k a -> FM k a -> BoolSource
FiniteMap operations
unionWithKey :: Ord k => ([k] -> a -> a -> a) -> FM k a -> FM k a -> FM k aSource
unionSeqWithKey :: (Ord k, Sequence seq) => ([k] -> a -> a -> a) -> seq (FM k a) -> FM k aSource
intersectionWithKey :: Ord k => ([k] -> a -> b -> c) -> FM k a -> FM k b -> FM k cSource
OrdAssocX operations
minView :: Monad m => FM k a -> m (a, FM k a)Source
minElem :: FM t1 t -> tSource
deleteMin :: Ord k => FM k a -> FM k aSource
unsafeInsertMin :: Ord k => [k] -> a -> FM k a -> FM k aSource
maxView :: Monad m => FM k a -> m (a, FM k a)Source
maxElem :: FM k a -> aSource
deleteMax :: Ord k => FM k a -> FM k aSource
unsafeInsertMax :: Ord k => [k] -> a -> FM k a -> FM k aSource
foldr :: Ord k => (a -> b -> b) -> b -> FM k a -> bSource
foldr' :: Ord k => (a -> b -> b) -> b -> FM k a -> bSource
foldr1 :: Ord k => (a -> a -> a) -> FM k a -> aSource
foldr1' :: Ord k => (a -> a -> a) -> FM k a -> aSource
foldl :: (a -> b -> a) -> a -> FM t b -> aSource
foldl' :: (a -> b -> a) -> a -> FM t b -> aSource
foldl1 :: (b -> b -> b) -> FM k b -> bSource
foldl1' :: (b -> b -> b) -> FM k b -> bSource
unsafeFromOrdSeq :: (Ord k, Sequence seq) => seq ([k], a) -> FM k aSource
unsafeAppend :: Ord k => FM k a -> FM k a -> FM k aSource
filterLT :: Ord k => [k] -> FM k a -> FM k aSource
filterLE :: Ord k => [k] -> FM k a -> FM k aSource
filterGT :: Ord k => [k] -> FM k a -> FM k aSource
filterGE :: Ord k => [k] -> FM k a -> FM k aSource
partitionLT_GE :: Ord k => [k] -> FM k a -> (FM k a, FM k a)Source
partitionLE_GT :: Ord k => [k] -> FM k a -> (FM k a, FM k a)Source
partitionLT_GT :: Ord k => [k] -> FM k a -> (FM k a, FM k a)Source
OrdAssoc operations
minViewWithKey :: Monad m => FM k a -> m (([k], a), FM k a)Source
minElemWithKey :: FM k a -> ([k], a)Source
maxViewWithKey :: Monad m => FM k a -> m (([k], a), FM k a)Source
maxElemWithKey :: FM k a -> ([k], a)Source
foldrWithKey :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> bSource
foldrWithKey' :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> bSource
foldlWithKey :: Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> bSource
foldlWithKey' :: Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> bSource
toOrdSeq :: (Ord k, Sequence seq) => FM k a -> seq ([k], a)Source
Other supported operations
mergeVFM :: Ord k => (Maybe a -> Maybe b -> Maybe c) -> FM k a -> FM k b -> FM k cSource
mergeKVFM :: Ord k => ([k] -> Maybe a -> Maybe b -> Maybe c) -> FM k a -> FM k b -> FM k cSource
Documentation
moduleName :: StringSource
Produced by Haddock version 2.3.0