Portability | GHC, Hugs (MPTC and FD) |
---|---|

Stability | stable |

Maintainer | robdockins AT fastmail DOT fm |

Safe Haskell | None |

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.

- 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)
- 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
- 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)
- moduleName :: String

# Type of little-endian Patricia trees

Functor FM | |

AssocX FM Int | |

OrdAssocX FM Int | |

FiniteMapX FM Int | |

OrdFiniteMapX FM Int | |

Assoc FM Int | |

OrdAssoc FM Int | |

FiniteMap FM Int | |

OrdFiniteMap FM Int | |

Eq a => Eq (FM a) | |

Ord a => Ord (FM a) | |

Read a => Read (FM a) | |

Show a => Show (FM a) | |

Arbitrary a => Arbitrary (FM a) | |

CoArbitrary a => CoArbitrary (FM a) | |

Monoid (FM a) |

# AssocX operations

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

strictWith :: (t -> a) -> FM t -> FM tSource

lookupWithDefault :: a -> Int -> FM a -> aSource

adjustOrInsert :: (a -> a) -> a -> Int -> FM a -> FM aSource

adjustAllOrInsert :: (a -> a) -> a -> Int -> FM a -> FM aSource

structuralInvariant :: FM a -> BoolSource

# Assoc operations

mapWithKey :: (Int -> a -> b) -> FM a -> FM bSource

foldWithKey :: (Int -> a -> b -> b) -> b -> FM a -> bSource

foldWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> bSource

# FiniteMapX operations

fromSeqWith :: Sequence seq => (a -> a -> a) -> seq (Int, a) -> FM aSource

insertWith :: (a -> a -> a) -> Int -> a -> FM a -> FM aSource

unionSeqWith :: Sequence seq => (a -> a -> a) -> seq (FM a) -> FM aSource

intersectionWith :: (a -> b -> c) -> FM a -> FM b -> FM cSource

difference :: FM a -> FM b -> FM aSource

properSubset :: FM a -> FM b -> BoolSource

# FiniteMap operations

# OrdAssocX operations

unsafeInsertMin :: Int -> a -> FM a -> FM aSource

unsafeInsertMax :: Int -> a -> FM a -> FM aSource

unsafeFromOrdSeq :: Sequence seq => seq (Int, a) -> FM aSource

unsafeAppend :: FM a -> FM a -> FM aSource

# OrdAssoc operations

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

maxElemWithKey :: FM a -> (Int, a)Source

foldrWithKey :: (Int -> a -> b -> b) -> b -> FM a -> bSource

foldrWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> bSource

foldlWithKey :: (b -> Int -> a -> b) -> b -> FM a -> bSource

foldlWithKey' :: (b -> Int -> a -> b) -> b -> FM a -> bSource