EdisonCore-1.3.2.1: A library of efficient, 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 Source #

Instances

Functor FM Source # 

Methods

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

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

AssocX FM Int Source # 

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

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

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 Source # 
Assoc FM Int Source # 

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

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

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 Source # 
Eq a => Eq (FM a) Source # 

Methods

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

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

Ord a => Ord (FM a) Source # 

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) Source # 
Show a => Show (FM a) Source # 

Methods

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

show :: FM a -> String #

showList :: [FM a] -> ShowS #

Semigroup (FM a) Source # 

Methods

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

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

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

Monoid (FM a) Source # 

Methods

mempty :: FM a #

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

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

Arbitrary a => Arbitrary (FM a) Source # 

Methods

arbitrary :: Gen (FM a) #

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

CoArbitrary a => CoArbitrary (FM a) Source # 

Methods

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

AssocX operations

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

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 :: Monad 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 :: Monad 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 :: Monad m => FM a -> m ((Int, a), FM a) Source #

maxViewWithKey :: Monad m => FM a -> m ((Int, a), FM 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