EdisonCore-1.2.1: A library of efficient, purely-functional data structures (Core Implementations) Contents Index

Data.Edison.Assoc.TernaryTrie Portability GHC, Hugs (MPTC and FD) Stability stable Maintainer robdockins 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) 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 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

Instances Ord k => Functor (FM k) Ord k => Assoc (FM k) [k] Ord k => AssocX (FM k) [k] Ord k => FiniteMap (FM k) [k] Ord k => FiniteMapX (FM k) [k] Ord k => OrdAssoc (FM k) [k] Ord k => OrdAssocX (FM k) [k] Ord k => OrdFiniteMap (FM k) [k] Ord k => OrdFiniteMapX (FM k) [k] (Ord k, Arbitrary k, Arbitrary a) => Arbitrary (FM k a) (Ord k, Eq a) => Eq (FM k a) Ord k => Monoid (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)

AssocX operations

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

Assoc operations

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)

FiniteMapX operations

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

FiniteMap operations

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

OrdAssocX operations

minView :: Monad m => FM k a -> m (a, FM k a)

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

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)

OrdAssoc operations

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)

Other supported operations

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

Documentation

moduleName :: String

Produced by Haddock version 0.8