EdisonCore-1.2.1.2: A library of efficent, purely-functional data structures (Core Implementations) Source code 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) 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

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 a Source

singleton :: Ord k => [k] -> a -> FM k a Source

fromSeq :: (Ord k, Sequence seq) => seq ([k], a) -> FM k a Source

insert :: Ord k => [k] -> a -> FM k a -> FM k a Source

insertSeq :: (Ord k, Sequence seq) => seq ([k], a) -> FM k a -> FM k a Source

union :: Ord k => FM k a -> FM k a -> FM k a Source

unionSeq :: (Ord k, Sequence seq) => seq (FM k a) -> FM k a Source

delete :: Ord k => [k] -> FM k a -> FM k a Source

deleteAll :: Ord k => [k] -> FM k a -> FM k a Source

deleteSeq :: (Ord k, Sequence seq) => seq [k] -> FM k a -> FM k a Source

null :: Ord k => FM k a -> Bool Source

size :: Ord k => FM k a -> Int Source

member :: Ord k => [k] -> FM k a -> Bool Source

count :: Ord k => [k] -> FM k a -> Int Source

lookup :: Ord k => [k] -> FM k a -> a Source

lookupM :: (Ord k, Monad rm) => [k] -> FM k a -> rm a Source

lookupAll :: (Ord k, Sequence seq) => [k] -> FM k a -> seq a Source

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 -> a Source

adjust :: Ord k => (a -> a) -> [k] -> FM k a -> FM k a Source

adjustAll :: Ord k => (a -> a) -> [k] -> FM k a -> FM k a Source

adjustOrInsert :: Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k a Source

adjustAllOrInsert :: Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k a Source

adjustOrDelete :: Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k a Source

adjustOrDeleteAll :: Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k a Source

strict :: FM k a -> FM k a Source

strictWith :: (a -> b) -> FM k a -> FM k a Source

map :: Ord k => (a -> b) -> FM k a -> FM k b Source

fold :: Ord k => (a -> b -> b) -> b -> FM k a -> b Source

fold' :: Ord k => (a -> b -> b) -> b -> FM k a -> b Source

fold1 :: Ord k => (a -> a -> a) -> FM k a -> a Source

fold1' :: Ord k => (a -> a -> a) -> FM k a -> a Source

filter :: Ord k => (a -> Bool) -> FM k a -> FM k a Source

partition :: Ord k => (a -> Bool) -> FM k a -> (FM k a, FM k a) Source

elements :: (Ord k, Sequence seq) => FM k a -> seq a Source

structuralInvariant :: Ord k => FM k a -> Bool Source

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 b Source

foldWithKey :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b Source

foldWithKey' :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b Source

filterWithKey :: Ord k => ([k] -> a -> Bool) -> FM k a -> FM k a Source

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 a Source

fromSeqWithKey :: (Ord k, Sequence seq) => ([k] -> a -> a -> a) -> seq ([k], a) -> FM k a Source

insertWith :: Ord k => (a -> a -> a) -> [k] -> a -> FM k a -> FM k a Source

insertWithKey :: Ord k => ([k] -> a -> a -> a) -> [k] -> a -> FM k a -> FM k a Source

insertSeqWith :: (Ord k, Sequence seq) => (a -> a -> a) -> seq ([k], a) -> FM k a -> FM k a Source

insertSeqWithKey :: (Ord k, Sequence seq) => ([k] -> a -> a -> a) -> seq ([k], a) -> FM k a -> FM k a Source

unionl :: Ord k => FM k a -> FM k a -> FM k a Source

unionr :: Ord k => FM k a -> FM k a -> FM k a Source

unionWith :: Ord k => (a -> a -> a) -> FM k a -> FM k a -> FM k a Source

unionSeqWith :: (Ord k, Sequence seq) => (a -> a -> a) -> seq (FM k a) -> FM k a Source

intersectionWith :: Ord k => (a -> b -> c) -> FM k a -> FM k b -> FM k c Source

difference :: Ord k => FM k a -> FM k b -> FM k a Source

properSubset :: Ord k => FM k a -> FM k b -> Bool Source

subset :: Ord k => FM k a -> FM k b -> Bool Source

properSubmapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool Source

submapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool Source

sameMapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool Source

properSubmap :: (Ord k, Eq a) => FM k a -> FM k a -> Bool Source

submap :: (Ord k, Eq a) => FM k a -> FM k a -> Bool Source

sameMap :: (Ord k, Eq a) => FM k a -> FM k a -> Bool Source

FiniteMap operations

unionWithKey :: Ord k => ([k] -> a -> a -> a) -> FM k a -> FM k a -> FM k a Source

unionSeqWithKey :: (Ord k, Sequence seq) => ([k] -> a -> a -> a) -> seq (FM k a) -> FM k a Source

intersectionWithKey :: Ord k => ([k] -> a -> b -> c) -> FM k a -> FM k b -> FM k c Source

OrdAssocX operations

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

minElem :: FM t1 t -> t Source

deleteMin :: Ord k => FM k a -> FM k a Source

unsafeInsertMin :: Ord k => [k] -> a -> FM k a -> FM k a Source

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

maxElem :: FM k a -> a Source

deleteMax :: Ord k => FM k a -> FM k a Source

unsafeInsertMax :: Ord k => [k] -> a -> FM k a -> FM k a Source

foldr :: Ord k => (a -> b -> b) -> b -> FM k a -> b Source

foldr' :: Ord k => (a -> b -> b) -> b -> FM k a -> b Source

foldr1 :: Ord k => (a -> a -> a) -> FM k a -> a Source

foldr1' :: Ord k => (a -> a -> a) -> FM k a -> a Source

foldl :: (a -> b -> a) -> a -> FM t b -> a Source

foldl' :: (a -> b -> a) -> a -> FM t b -> a Source

foldl1 :: (b -> b -> b) -> FM k b -> b Source

foldl1' :: (b -> b -> b) -> FM k b -> b Source

unsafeFromOrdSeq :: (Ord k, Sequence seq) => seq ([k], a) -> FM k a Source

unsafeAppend :: Ord k => FM k a -> FM k a -> FM k a Source

filterLT :: Ord k => [k] -> FM k a -> FM k a Source

filterLE :: Ord k => [k] -> FM k a -> FM k a Source

filterGT :: Ord k => [k] -> FM k a -> FM k a Source

filterGE :: Ord k => [k] -> FM k a -> FM k a Source

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 -> b Source

foldrWithKey' :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b Source

foldlWithKey :: Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> b Source

foldlWithKey' :: Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> b Source

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 c Source

mergeKVFM :: Ord k => ([k] -> Maybe a -> Maybe b -> Maybe c) -> FM k a -> FM k b -> FM k c Source

Documentation

moduleName :: String Source

Produced by Haddock version 2.3.0