 | EdisonCore-1.2.1: A library of efficient, purely-functional data structures (Core Implementations) | Contents | Index |
|
| Data.Edison.Assoc.PatriciaLoMap | | Portability | GHC, Hugs (MPTC and FD) | | Stability | stable | | Maintainer | robdockins AT fastmail DOT fm |
|
|
|
|
|
| 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 :: 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) | | | 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 :: 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) | | | 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) |
|
|
|
| Type of little-endian Patricia trees
|
|
| data FM a |
 Instances | |
|
|
| 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) |
|
| 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 |
|
| 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
|
|
| Produced by Haddock version 0.8 |