EdisonCore-1.3.1.1: A library of efficent, purely-functional data structures (Core Implementations)

CopyrightCopyright (c) 1998 2008 Chris Okasaki
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.PatriciaLoMap

Contents

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

Type of little-endian Patricia trees

data FM a #

Instances

Functor FM # 

Methods

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

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

AssocX FM Int # 

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 :: Monad rm => Int -> FM a -> rm a #

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

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

lookupAndDeleteM :: Monad 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 #

OrdAssocX FM Int # 

Methods

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

minElem :: FM a -> a #

deleteMin :: FM a -> FM a #

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

maxView :: Monad 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) #

FiniteMapX FM Int # 

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 #

OrdFiniteMapX FM Int # 
Assoc FM Int # 

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) #

OrdAssoc FM Int # 

Methods

minViewWithKey :: Monad rm => FM a -> rm ((Int, a), FM a) #

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

maxViewWithKey :: Monad 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) #

FiniteMap FM Int # 

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 #

OrdFiniteMap FM Int # 
Eq a => Eq (FM a) # 

Methods

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

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

Ord a => Ord (FM a) # 

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 #

Read a => Read (FM a) # 
Show a => Show (FM a) # 

Methods

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

show :: FM a -> String #

showList :: [FM a] -> ShowS #

Monoid (FM a) # 

Methods

mempty :: FM a #

mappend :: FM a -> FM a -> FM a #

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

Arbitrary a => Arbitrary (FM a) # 

Methods

arbitrary :: Gen (FM a) #

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

CoArbitrary a => CoArbitrary (FM a) # 

Methods

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

AssocX operations

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 :: Monad rm => Int -> FM a -> rm a #

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

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

lookupAndDeleteM :: Monad 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 #

Assoc operations

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) #

FiniteMapX operations

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 #

FiniteMap operations

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 #

OrdAssocX operations

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

minElem :: FM a -> a #

deleteMin :: FM a -> FM a #

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

maxView :: Monad 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) #

OrdAssoc operations

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

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

maxViewWithKey :: Monad 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) #

Documentation