EdisonCore-1.3.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

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

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