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	None
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

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 #
Methods readsPrec :: Int -> ReadS (FM a) # readList :: ReadS [FM a] # readPrec :: ReadPrec (FM a) # readListPrec :: ReadPrec [FM a] #
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 #