Copyright	Copyright (c) 1998 2008 Chris Okasaki
License	MIT; see COPYRIGHT file for terms and conditions
Maintainer	robdockins AT fastmail DOT fm
Stability	stable
Portability	GHC, Hugs (MPTC and FD)
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Edison.Assoc.PatriciaLoMap

Contents

Type of little-endian Patricia trees
AssocX operations
Assoc operations
FiniteMapX operations
FiniteMap operations
OrdAssocX operations
OrdAssoc operations
Documentation

Description

Finite maps implemented as little-endian Patricia trees.

References:

Chris Okasaki and Any Gill. "Fast Mergeable Integer Maps". Workshop on ML, September 1998, pages 77-86.

Synopsis

data FM a
empty :: FM a
singleton :: Int -> a -> FM a
fromSeq :: Sequence seq => seq (Int, a) -> FM a
insert :: Int -> a -> FM a -> FM a
insertSeq :: Sequence seq => seq (Int, a) -> FM a -> FM a
union :: FM a -> FM a -> FM a
unionSeq :: Sequence seq => seq (FM a) -> FM a
delete :: Int -> FM a -> FM a
deleteAll :: Int -> FM a -> FM a
deleteSeq :: Sequence seq => seq Int -> FM a -> FM a
null :: FM a -> Bool
size :: FM a -> Int
member :: Int -> FM a -> Bool
count :: Int -> FM a -> Int
lookup :: Int -> FM a -> a
lookupM :: MonadFail rm => Int -> FM a -> rm a
lookupAll :: Sequence seq => Int -> FM a -> seq a
lookupAndDelete :: Int -> FM a -> (a, FM a)
lookupAndDeleteM :: MonadFail m => Int -> FM a -> m (a, FM a)
lookupAndDeleteAll :: Sequence seq => Int -> FM a -> (seq a, FM a)
strict :: t -> t
strictWith :: (t -> a) -> FM t -> FM t
lookupWithDefault :: a -> Int -> FM a -> a
adjust :: (a -> a) -> Int -> FM a -> FM a
adjustAll :: (a -> a) -> Int -> FM a -> FM a
adjustOrInsert :: (a -> a) -> a -> Int -> FM a -> FM a
adjustAllOrInsert :: (a -> a) -> a -> Int -> FM a -> FM a
map :: (a -> b) -> FM a -> FM b
fold :: (a -> b -> b) -> b -> FM a -> b
fold' :: (a -> b -> b) -> b -> FM a -> b
fold1 :: (a -> a -> a) -> FM a -> a
fold1' :: (a -> a -> a) -> FM a -> a
filter :: (a -> Bool) -> FM a -> FM a
partition :: (a -> Bool) -> FM a -> (FM a, FM a)
elements :: Sequence seq => FM a -> seq a
structuralInvariant :: FM a -> Bool
toSeq :: Sequence seq => FM a -> seq (Int, a)
keys :: Sequence seq => FM a -> seq Int
mapWithKey :: (Int -> a -> b) -> FM a -> FM b
foldWithKey :: (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> b
filterWithKey :: (Int -> a -> Bool) -> FM a -> FM a
partitionWithKey :: (Int -> a -> Bool) -> FM a -> (FM a, FM a)
fromSeqWith :: Sequence seq => (a -> a -> a) -> seq (Int, a) -> FM a
fromSeqWithKey :: Sequence seq => (Int -> a -> a -> a) -> seq (Int, a) -> FM a
insertWith :: (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWithKey :: (Int -> a -> a -> a) -> Int -> a -> FM a -> FM a
insertSeqWith :: Sequence seq => (a -> a -> a) -> seq (Int, a) -> FM a -> FM a
insertSeqWithKey :: Sequence seq => (Int -> a -> a -> a) -> seq (Int, a) -> FM a -> FM a
unionl :: FM a -> FM a -> FM a
unionr :: FM a -> FM a -> FM a
unionWith :: (a -> a -> a) -> FM a -> FM a -> FM a
unionSeqWith :: Sequence seq => (a -> a -> a) -> seq (FM a) -> FM a
intersectionWith :: (a -> b -> c) -> FM a -> FM b -> FM c
difference :: FM a -> FM b -> FM a
properSubset :: FM a -> FM b -> Bool
subset :: FM a -> FM b -> Bool
properSubmapBy :: (a -> a -> Bool) -> FM a -> FM a -> Bool
submapBy :: (a -> a -> Bool) -> FM a -> FM a -> Bool
sameMapBy :: (a -> a -> Bool) -> FM a -> FM a -> Bool
properSubmap :: Eq a => FM a -> FM a -> Bool
submap :: Eq a => FM a -> FM a -> Bool
sameMap :: Eq a => FM a -> FM a -> Bool
unionWithKey :: (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionSeqWithKey :: Sequence seq => (Int -> a -> a -> a) -> seq (FM a) -> FM a
intersectionWithKey :: (Int -> a -> b -> c) -> FM a -> FM b -> FM c
minView :: MonadFail m => FM a -> m (a, FM a)
minElem :: FM a -> a
deleteMin :: FM a -> FM a
unsafeInsertMin :: Int -> a -> FM a -> FM a
maxView :: MonadFail m => FM a -> m (a, FM a)
maxElem :: FM a -> a
deleteMax :: FM a -> FM a
unsafeInsertMax :: Int -> a -> FM a -> FM a
foldr :: (a -> b -> b) -> b -> FM a -> b
foldr' :: (a -> b -> b) -> b -> FM a -> b
foldr1 :: (a -> a -> a) -> FM a -> a
foldr1' :: (a -> a -> a) -> FM a -> a
foldl :: (b -> a -> b) -> b -> FM a -> b
foldl' :: (b -> a -> b) -> b -> FM a -> b
foldl1 :: (a -> a -> a) -> FM a -> a
foldl1' :: (a -> a -> a) -> FM a -> a
unsafeFromOrdSeq :: Sequence seq => seq (Int, a) -> FM a
unsafeAppend :: FM a -> FM a -> FM a
filterLT :: Int -> FM a -> FM a
filterLE :: Int -> FM a -> FM a
filterGT :: Int -> FM a -> FM a
filterGE :: Int -> FM a -> FM a
partitionLT_GE :: Int -> FM a -> (FM a, FM a)
partitionLE_GT :: Int -> FM a -> (FM a, FM a)
partitionLT_GT :: Int -> FM a -> (FM a, FM a)
minViewWithKey :: MonadFail m => FM a -> m ((Int, a), FM a)
minElemWithKey :: FM a -> (Int, a)
maxViewWithKey :: MonadFail m => FM a -> m ((Int, a), FM a)
maxElemWithKey :: FM a -> (Int, a)
foldrWithKey :: (Int -> a -> b -> b) -> b -> FM a -> b
foldrWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> b
foldlWithKey :: (b -> Int -> a -> b) -> b -> FM a -> b
foldlWithKey' :: (b -> Int -> a -> b) -> b -> FM a -> b
toOrdSeq :: Sequence seq => FM a -> seq (Int, a)
moduleName :: String

Type of little-endian Patricia trees

data FM a Source #

Instances

Instances details

Functor FM Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods fmap :: (a -> b) -> FM a -> FM b # (<$) :: a -> FM b -> FM a #
Assoc FM Int Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods toSeq :: Sequence seq => FM a -> seq (Int, a) # keys :: Sequence seq => FM a -> seq Int # mapWithKey :: (Int -> a -> b) -> FM a -> FM b # foldWithKey :: (Int -> a -> b -> b) -> b -> FM a -> b # foldWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> b # filterWithKey :: (Int -> a -> Bool) -> FM a -> FM a # partitionWithKey :: (Int -> a -> Bool) -> FM a -> (FM a, FM a) #
AssocX FM Int Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods empty :: FM a # singleton :: Int -> a -> FM a # fromSeq :: Sequence seq => seq (Int, a) -> FM a # insert :: Int -> a -> FM a -> FM a # insertSeq :: Sequence seq => seq (Int, a) -> FM a -> FM a # union :: FM a -> FM a -> FM a # unionSeq :: Sequence seq => seq (FM a) -> FM a # delete :: Int -> FM a -> FM a # deleteAll :: Int -> FM a -> FM a # deleteSeq :: Sequence seq => seq Int -> FM a -> FM a # null :: FM a -> Bool # size :: FM a -> Int # member :: Int -> FM a -> Bool # count :: Int -> FM a -> Int # lookup :: Int -> FM a -> a # lookupM :: MonadFail rm => Int -> FM a -> rm a # lookupAll :: Sequence seq => Int -> FM a -> seq a # lookupAndDelete :: Int -> FM a -> (a, FM a) # lookupAndDeleteM :: MonadFail rm => Int -> FM a -> rm (a, FM a) # lookupAndDeleteAll :: Sequence seq => Int -> FM a -> (seq a, FM a) # lookupWithDefault :: a -> Int -> FM a -> a # adjust :: (a -> a) -> Int -> FM a -> FM a # adjustAll :: (a -> a) -> Int -> FM a -> FM a # adjustOrInsert :: (a -> a) -> a -> Int -> FM a -> FM a # adjustAllOrInsert :: (a -> a) -> a -> Int -> FM a -> FM a # adjustOrDelete :: (a -> Maybe a) -> Int -> FM a -> FM a # adjustOrDeleteAll :: (a -> Maybe a) -> Int -> FM a -> FM a # fold :: (a -> b -> b) -> b -> FM a -> b # fold' :: (a -> b -> b) -> b -> FM a -> b # fold1 :: (a -> a -> a) -> FM a -> a # fold1' :: (a -> a -> a) -> FM a -> a # filter :: (a -> Bool) -> FM a -> FM a # partition :: (a -> Bool) -> FM a -> (FM a, FM a) # elements :: Sequence seq => FM a -> seq a # strict :: FM a -> FM a # strictWith :: (a -> b) -> FM a -> FM a # structuralInvariant :: FM a -> Bool # instanceName :: FM a -> String #
FiniteMap FM Int Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods unionWithKey :: (Int -> a -> a -> a) -> FM a -> FM a -> FM a # unionSeqWithKey :: Sequence seq => (Int -> a -> a -> a) -> seq (FM a) -> FM a # intersectionWithKey :: (Int -> a -> b -> c) -> FM a -> FM b -> FM c #
FiniteMapX FM Int Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods fromSeqWith :: Sequence seq => (a -> a -> a) -> seq (Int, a) -> FM a # fromSeqWithKey :: Sequence seq => (Int -> a -> a -> a) -> seq (Int, a) -> FM a # insertWith :: (a -> a -> a) -> Int -> a -> FM a -> FM a # insertWithKey :: (Int -> a -> a -> a) -> Int -> a -> FM a -> FM a # insertSeqWith :: Sequence seq => (a -> a -> a) -> seq (Int, a) -> FM a -> FM a # insertSeqWithKey :: Sequence seq => (Int -> a -> a -> a) -> seq (Int, a) -> FM a -> FM a # unionl :: FM a -> FM a -> FM a # unionr :: FM a -> FM a -> FM a # unionWith :: (a -> a -> a) -> FM a -> FM a -> FM a # unionSeqWith :: Sequence seq => (a -> a -> a) -> seq (FM a) -> FM a # intersectionWith :: (a -> b -> c) -> FM a -> FM b -> FM c # difference :: FM a -> FM b -> FM a # properSubset :: FM a -> FM b -> Bool # subset :: FM a -> FM b -> Bool # submapBy :: (a -> a -> Bool) -> FM a -> FM a -> Bool # properSubmapBy :: (a -> a -> Bool) -> FM a -> FM a -> Bool # sameMapBy :: (a -> a -> Bool) -> FM a -> FM a -> Bool #
OrdAssoc FM Int Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods minViewWithKey :: MonadFail rm => FM a -> rm ((Int, a), FM a) # minElemWithKey :: FM a -> (Int, a) # maxViewWithKey :: MonadFail rm => FM a -> rm ((Int, a), FM a) # maxElemWithKey :: FM a -> (Int, a) # foldrWithKey :: (Int -> a -> b -> b) -> b -> FM a -> b # foldrWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> b # foldlWithKey :: (b -> Int -> a -> b) -> b -> FM a -> b # foldlWithKey' :: (b -> Int -> a -> b) -> b -> FM a -> b # toOrdSeq :: Sequence seq => FM a -> seq (Int, a) #
OrdAssocX FM Int Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods minView :: MonadFail rm => FM a -> rm (a, FM a) # minElem :: FM a -> a # deleteMin :: FM a -> FM a # unsafeInsertMin :: Int -> a -> FM a -> FM a # maxView :: MonadFail rm => FM a -> rm (a, FM a) # maxElem :: FM a -> a # deleteMax :: FM a -> FM a # unsafeInsertMax :: Int -> a -> FM a -> FM a # foldr :: (a -> b -> b) -> b -> FM a -> b # foldr' :: (a -> b -> b) -> b -> FM a -> b # foldl :: (b -> a -> b) -> b -> FM a -> b # foldl' :: (b -> a -> b) -> b -> FM a -> b # foldr1 :: (a -> a -> a) -> FM a -> a # foldr1' :: (a -> a -> a) -> FM a -> a # foldl1 :: (a -> a -> a) -> FM a -> a # foldl1' :: (a -> a -> a) -> FM a -> a # unsafeFromOrdSeq :: Sequence seq => seq (Int, a) -> FM a # unsafeAppend :: FM a -> FM a -> FM a # filterLT :: Int -> FM a -> FM a # filterLE :: Int -> FM a -> FM a # filterGT :: Int -> FM a -> FM a # filterGE :: Int -> FM a -> FM a # partitionLT_GE :: Int -> FM a -> (FM a, FM a) # partitionLE_GT :: Int -> FM a -> (FM a, FM a) # partitionLT_GT :: Int -> FM a -> (FM a, FM a) #
OrdFiniteMap FM Int Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap
OrdFiniteMapX FM Int Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap
Arbitrary a => Arbitrary (FM a) Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods arbitrary :: Gen (FM a) # shrink :: FM a -> [FM a] #
CoArbitrary a => CoArbitrary (FM a) Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods coarbitrary :: FM a -> Gen b -> Gen b #
Monoid (FM a) Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods mempty :: FM a # mappend :: FM a -> FM a -> FM a # mconcat :: [FM a] -> FM a #
Semigroup (FM a) Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods (<>) :: FM a -> FM a -> FM a # sconcat :: NonEmpty (FM a) -> FM a # stimes :: Integral b => b -> FM a -> FM a #
Read a => Read (FM a) Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods readsPrec :: Int -> ReadS (FM a) # readList :: ReadS [FM a] # readPrec :: ReadPrec (FM a) # readListPrec :: ReadPrec [FM a] #
Show a => Show (FM a) Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods showsPrec :: Int -> FM a -> ShowS # show :: FM a -> String # showList :: [FM a] -> ShowS #
Eq a => Eq (FM a) Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods (==) :: FM a -> FM a -> Bool # (/=) :: FM a -> FM a -> Bool #
Ord a => Ord (FM a) Source #
Instance details Defined in Data.Edison.Assoc.PatriciaLoMap Methods compare :: FM a -> FM a -> Ordering # (<) :: FM a -> FM a -> Bool # (<=) :: FM a -> FM a -> Bool # (>) :: FM a -> FM a -> Bool # (>=) :: FM a -> FM a -> Bool # max :: FM a -> FM a -> FM a # min :: FM a -> FM a -> FM a #

AssocX operations

empty :: FM a Source #

singleton :: Int -> a -> FM a Source #

fromSeq :: Sequence seq => seq (Int, a) -> FM a Source #

insert :: Int -> a -> FM a -> FM a Source #

insertSeq :: Sequence seq => seq (Int, a) -> FM a -> FM a Source #

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

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

delete :: Int -> FM a -> FM a Source #

deleteAll :: Int -> FM a -> FM a Source #

deleteSeq :: Sequence seq => seq Int -> FM a -> FM a Source #

null :: FM a -> Bool Source #

size :: FM a -> Int Source #

member :: Int -> FM a -> Bool Source #

count :: Int -> FM a -> Int Source #

lookup :: Int -> FM a -> a Source #

lookupM :: MonadFail rm => Int -> FM a -> rm a Source #

lookupAll :: Sequence seq => Int -> FM a -> seq a Source #

lookupAndDelete :: Int -> FM a -> (a, FM a) Source #

lookupAndDeleteM :: MonadFail m => Int -> FM a -> m (a, FM a) Source #

lookupAndDeleteAll :: Sequence seq => Int -> FM a -> (seq a, FM a) Source #

strict :: t -> t Source #

strictWith :: (t -> a) -> FM t -> FM t Source #

lookupWithDefault :: a -> Int -> FM a -> a Source #

adjust :: (a -> a) -> Int -> FM a -> FM a Source #

adjustAll :: (a -> a) -> Int -> FM a -> FM a Source #

adjustOrInsert :: (a -> a) -> a -> Int -> FM a -> FM a Source #

adjustAllOrInsert :: (a -> a) -> a -> Int -> FM a -> FM a Source #

map :: (a -> b) -> FM a -> FM b Source #

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

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

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

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

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

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

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

structuralInvariant :: FM a -> Bool Source #

Assoc operations

toSeq :: Sequence seq => FM a -> seq (Int, a) Source #

keys :: Sequence seq => FM a -> seq Int Source #

mapWithKey :: (Int -> a -> b) -> FM a -> FM b Source #

foldWithKey :: (Int -> a -> b -> b) -> b -> FM a -> b Source #

foldWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> b Source #

filterWithKey :: (Int -> a -> Bool) -> FM a -> FM a Source #

partitionWithKey :: (Int -> a -> Bool) -> FM a -> (FM a, FM a) Source #

FiniteMapX operations

fromSeqWith :: Sequence seq => (a -> a -> a) -> seq (Int, a) -> FM a Source #

fromSeqWithKey :: Sequence seq => (Int -> a -> a -> a) -> seq (Int, a) -> FM a Source #

insertWith :: (a -> a -> a) -> Int -> a -> FM a -> FM a Source #

insertWithKey :: (Int -> a -> a -> a) -> Int -> a -> FM a -> FM a Source #

insertSeqWith :: Sequence seq => (a -> a -> a) -> seq (Int, a) -> FM a -> FM a Source #

insertSeqWithKey :: Sequence seq => (Int -> a -> a -> a) -> seq (Int, a) -> FM a -> FM a Source #

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

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

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

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

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

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

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

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

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

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

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

properSubmap :: Eq a => FM a -> FM a -> Bool Source #

submap :: Eq a => FM a -> FM a -> Bool Source #

sameMap :: Eq a => FM a -> FM a -> Bool Source #

FiniteMap operations

unionWithKey :: (Int -> a -> a -> a) -> FM a -> FM a -> FM a Source #

unionSeqWithKey :: Sequence seq => (Int -> a -> a -> a) -> seq (FM a) -> FM a Source #

intersectionWithKey :: (Int -> a -> b -> c) -> FM a -> FM b -> FM c Source #

OrdAssocX operations

minView :: MonadFail m => FM a -> m (a, FM a) Source #

minElem :: FM a -> a Source #

deleteMin :: FM a -> FM a Source #

unsafeInsertMin :: Int -> a -> FM a -> FM a Source #

maxView :: MonadFail m => FM a -> m (a, FM a) Source #

maxElem :: FM a -> a Source #

deleteMax :: FM a -> FM a Source #

unsafeInsertMax :: Int -> a -> FM a -> FM a Source #

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

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

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

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

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

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

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

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

unsafeFromOrdSeq :: Sequence seq => seq (Int, a) -> FM a Source #

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

filterLT :: Int -> FM a -> FM a Source #

filterLE :: Int -> FM a -> FM a Source #

filterGT :: Int -> FM a -> FM a Source #

filterGE :: Int -> FM a -> FM a Source #

partitionLT_GE :: Int -> FM a -> (FM a, FM a) Source #

partitionLE_GT :: Int -> FM a -> (FM a, FM a) Source #

partitionLT_GT :: Int -> FM a -> (FM a, FM a) Source #

OrdAssoc operations

minViewWithKey :: MonadFail m => FM a -> m ((Int, a), FM a) Source #

minElemWithKey :: FM a -> (Int, a) Source #

maxViewWithKey :: MonadFail m => FM a -> m ((Int, a), FM a) Source #

maxElemWithKey :: FM a -> (Int, a) Source #

foldrWithKey :: (Int -> a -> b -> b) -> b -> FM a -> b Source #

foldrWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> b Source #

foldlWithKey :: (b -> Int -> a -> b) -> b -> FM a -> b Source #

foldlWithKey' :: (b -> Int -> a -> b) -> b -> FM a -> b Source #

toOrdSeq :: Sequence seq => FM a -> seq (Int, a) Source #

Documentation

moduleName :: String Source #

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result