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 |

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

AssocX FM Int Source | |

OrdAssocX FM Int Source | |

FiniteMapX FM Int Source | |

OrdFiniteMapX FM Int Source | |

Assoc FM Int Source | |

OrdAssoc FM Int Source | |

FiniteMap FM Int Source | |

OrdFiniteMap FM Int Source | |

Eq a => Eq (FM a) Source | |

Ord a => Ord (FM a) Source | |

Read a => Read (FM a) Source | |

Show a => Show (FM a) Source | |

Arbitrary a => Arbitrary (FM a) Source | |

CoArbitrary a => CoArbitrary (FM a) Source | |

Monoid (FM a) Source |

# AssocX operations

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

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

lookupWithDefault :: a -> Int -> FM a -> a Source

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

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

structuralInvariant :: FM a -> Bool Source

# Assoc operations

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

# FiniteMapX operations

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

insertWith :: (a -> a -> a) -> Int -> 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

# FiniteMap operations

# OrdAssocX operations

unsafeInsertMin :: Int -> a -> FM a -> FM a Source

unsafeInsertMax :: Int -> a -> FM a -> FM a Source

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

unsafeAppend :: FM a -> FM a -> FM a Source

# OrdAssoc operations

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

maxElemWithKey :: FM a -> (Int, 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