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

CopyrightCopyright (c) 2002 2008 Andrew Bromage
LicenseMIT; see COPYRIGHT file for terms and conditions
Maintainerrobdockins AT fastmail DOT fm
Stabilitystable
PortabilityGHC, Hugs (MPTC and FD)
Safe HaskellNone
LanguageHaskell2010

Data.Edison.Assoc.TernaryTrie

Contents

Description

Finite maps implemented as ternary search tries

Synopsis

Type of ternary search tries

data FM k a Source #

Instances
Ord k => Functor (FM k) Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

fmap :: (a -> b) -> FM k a -> FM k b

(<$) :: a -> FM k b -> FM k a

Ord k => AssocX (FM k) [k] Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

empty :: FM k a Source #

singleton :: [k] -> a -> FM k a Source #

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

insert :: [k] -> a -> FM k a -> FM k a Source #

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

union :: FM k a -> FM k a -> FM k a Source #

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

delete :: [k] -> FM k a -> FM k a Source #

deleteAll :: [k] -> FM k a -> FM k a Source #

deleteSeq :: Sequence seq => seq [k] -> FM k a -> FM k a Source #

null :: FM k a -> Bool Source #

size :: FM k a -> Int Source #

member :: [k] -> FM k a -> Bool Source #

count :: [k] -> FM k a -> Int Source #

lookup :: [k] -> FM k a -> a Source #

lookupM :: Monad rm => [k] -> FM k a -> rm a Source #

lookupAll :: Sequence seq => [k] -> FM k a -> seq a Source #

lookupAndDelete :: [k] -> FM k a -> (a, FM k a) Source #

lookupAndDeleteM :: Monad rm => [k] -> FM k a -> rm (a, FM k a) Source #

lookupAndDeleteAll :: Sequence seq => [k] -> FM k a -> (seq a, FM k a) Source #

lookupWithDefault :: a -> [k] -> FM k a -> a Source #

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

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

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

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

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

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

fold :: (a -> b -> b) -> b -> FM k a -> b Source #

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

fold1 :: (a -> a -> a) -> FM k a -> a Source #

fold1' :: (a -> a -> a) -> FM k a -> a Source #

filter :: (a -> Bool) -> FM k a -> FM k a Source #

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

elements :: Sequence seq => FM k a -> seq a Source #

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

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

structuralInvariant :: FM k a -> Bool Source #

instanceName :: FM k a -> String Source #

Ord k => OrdAssocX (FM k) [k] Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

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

minElem :: FM k a -> a Source #

deleteMin :: FM k a -> FM k a Source #

unsafeInsertMin :: [k] -> a -> FM k a -> FM k a Source #

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

maxElem :: FM k a -> a Source #

deleteMax :: FM k a -> FM k a Source #

unsafeInsertMax :: [k] -> a -> FM k a -> FM k a Source #

foldr :: (a -> b -> b) -> b -> FM k a -> b Source #

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

foldl :: (b -> a -> b) -> b -> FM k a -> b Source #

foldl' :: (b -> a -> b) -> b -> FM k a -> b Source #

foldr1 :: (a -> a -> a) -> FM k a -> a Source #

foldr1' :: (a -> a -> a) -> FM k a -> a Source #

foldl1 :: (a -> a -> a) -> FM k a -> a Source #

foldl1' :: (a -> a -> a) -> FM k a -> a Source #

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

unsafeAppend :: FM k a -> FM k a -> FM k a Source #

filterLT :: [k] -> FM k a -> FM k a Source #

filterLE :: [k] -> FM k a -> FM k a Source #

filterGT :: [k] -> FM k a -> FM k a Source #

filterGE :: [k] -> FM k a -> FM k a Source #

partitionLT_GE :: [k] -> FM k a -> (FM k a, FM k a) Source #

partitionLE_GT :: [k] -> FM k a -> (FM k a, FM k a) Source #

partitionLT_GT :: [k] -> FM k a -> (FM k a, FM k a) Source #

Ord k => FiniteMapX (FM k) [k] Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

fromSeqWith :: Sequence seq => (a -> a -> a) -> seq ([k], a) -> FM k a Source #

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

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

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

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

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

unionl :: FM k a -> FM k a -> FM k a Source #

unionr :: FM k a -> FM k a -> FM k a Source #

unionWith :: (a -> a -> a) -> FM k a -> FM k a -> FM k a Source #

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

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

difference :: FM k a -> FM k b -> FM k a Source #

properSubset :: FM k a -> FM k b -> Bool Source #

subset :: FM k a -> FM k b -> Bool Source #

submapBy :: (a -> a -> Bool) -> FM k a -> FM k a -> Bool Source #

properSubmapBy :: (a -> a -> Bool) -> FM k a -> FM k a -> Bool Source #

sameMapBy :: (a -> a -> Bool) -> FM k a -> FM k a -> Bool Source #

Ord k => OrdFiniteMapX (FM k) [k] Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Ord k => Assoc (FM k) [k] Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

toSeq :: Sequence seq => FM k a -> seq ([k], a) Source #

keys :: Sequence seq => FM k a -> seq [k] Source #

mapWithKey :: ([k] -> a -> b) -> FM k a -> FM k b Source #

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

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

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

partitionWithKey :: ([k] -> a -> Bool) -> FM k a -> (FM k a, FM k a) Source #

Ord k => OrdAssoc (FM k) [k] Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

minViewWithKey :: Monad rm => FM k a -> rm (([k], a), FM k a) Source #

minElemWithKey :: FM k a -> ([k], a) Source #

maxViewWithKey :: Monad rm => FM k a -> rm (([k], a), FM k a) Source #

maxElemWithKey :: FM k a -> ([k], a) Source #

foldrWithKey :: ([k] -> a -> b -> b) -> b -> FM k a -> b Source #

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

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

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

toOrdSeq :: Sequence seq => FM k a -> seq ([k], a) Source #

Ord k => FiniteMap (FM k) [k] Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

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

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

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

Ord k => OrdFiniteMap (FM k) [k] Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

(Ord k, Eq a) => Eq (FM k a) Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

(==) :: FM k a -> FM k a -> Bool

(/=) :: FM k a -> FM k a -> Bool

(Ord k, Ord a) => Ord (FM k a) Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

compare :: FM k a -> FM k a -> Ordering

(<) :: FM k a -> FM k a -> Bool

(<=) :: FM k a -> FM k a -> Bool

(>) :: FM k a -> FM k a -> Bool

(>=) :: FM k a -> FM k a -> Bool

max :: FM k a -> FM k a -> FM k a

min :: FM k a -> FM k a -> FM k a

(Ord k, Read k, Read a) => Read (FM k a) Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

readsPrec :: Int -> ReadS (FM k a)

readList :: ReadS [FM k a]

readPrec :: ReadPrec (FM k a)

readListPrec :: ReadPrec [FM k a]

(Ord k, Show k, Show a) => Show (FM k a) Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

showsPrec :: Int -> FM k a -> ShowS

show :: FM k a -> String

showList :: [FM k a] -> ShowS

Ord k => Semigroup (FM k a) Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

(<>) :: FM k a -> FM k a -> FM k a

sconcat :: NonEmpty (FM k a) -> FM k a

stimes :: Integral b => b -> FM k a -> FM k a

Ord k => Monoid (FM k a) Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

mempty :: FM k a

mappend :: FM k a -> FM k a -> FM k a

mconcat :: [FM k a] -> FM k a

(Ord k, Arbitrary k, Arbitrary a) => Arbitrary (FM k a) Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

arbitrary :: Gen (FM k a)

shrink :: FM k a -> [FM k a]

(Ord k, CoArbitrary k, CoArbitrary a) => CoArbitrary (FM k a) Source # 
Instance details

Defined in Data.Edison.Assoc.TernaryTrie

Methods

coarbitrary :: FM k a -> Gen b -> Gen b

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 #