| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.HashCons.WordMap.Internal
Description
This module provides an efficient implementation of maps from Word keys to values.
It uses a Patricia trie with hash-consing to enable fast structural sharing and
O(1) equality checks. The HashCons type wraps the internal nodes to take advantage
of O(1) Eq and Ord operations provided by hash-consing.
Note: This is an internal module. Users should prefer the public interface provided
by WordMap.
Synopsis
- data WordMap a
- = Empty
- | NonEmptyMap !(HashCons (NonEmptyWordMap a))
- data NonEmptyWordMap a
- empty :: WordMap a
- singleton :: Hashable a => Word -> a -> WordMap a
- singletonNonEmpty :: Hashable a => Word -> a -> NonEmptyWordMap a
- insert :: Hashable a => Word -> a -> WordMap a -> WordMap a
- insertNonEmpty :: Hashable a => Word -> a -> NonEmptyWordMap a -> NonEmptyWordMap a
- lookup :: Word -> WordMap a -> Maybe a
- lookupNonEmpty :: Word -> NonEmptyWordMap a -> Maybe a
- map :: Hashable b => (a -> b) -> WordMap a -> WordMap b
- mapNonEmpty :: Hashable b => (a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
- mapWithKey :: Hashable b => (Word -> a -> b) -> WordMap a -> WordMap b
- mapWithKeyNonEmpty :: Hashable b => (Word -> a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
- traverseWithKey :: (Applicative t, Hashable b) => (Word -> a -> t b) -> WordMap a -> t (WordMap b)
- traverseWithKeyNonEmpty :: (Applicative t, Hashable b) => (Word -> a -> t b) -> NonEmptyWordMap a -> t (NonEmptyWordMap b)
- union :: Hashable a => WordMap a -> WordMap a -> WordMap a
- unionNonEmpty :: Hashable a => NonEmptyWordMap a -> WordMap a -> NonEmptyWordMap a
- unionNonEmptyNonEmpty :: Hashable a => NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
- intersection :: Hashable a => WordMap a -> WordMap a -> WordMap a
- intersectionNonEmpty :: Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a
- difference :: Hashable a => WordMap a -> WordMap a -> WordMap a
- differenceNonEmpty :: Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a
- member :: Word -> WordMap a -> Bool
- memberNonEmpty :: Word -> NonEmptyWordMap a -> Bool
- combine :: Hashable a => Word -> Word -> WordMap a -> WordMap a -> WordMap a
- join :: Hashable a => Word -> NonEmptyWordMap a -> Word -> NonEmptyWordMap a -> NonEmptyWordMap a
- match :: Word -> Word -> Word -> Bool
- mask :: Word -> Word -> Word
- zero :: Word -> Word -> Bool
- branchingBit :: Word -> Word -> Word
- highestBitMask :: Word -> Word
- shorter :: Word -> Word -> Bool
Documentation
The main WordMap data type.
Constructors
| Empty | |
| NonEmptyMap !(HashCons (NonEmptyWordMap a)) |
Instances
data NonEmptyWordMap a Source #
Non-empty trie nodes.
Instances
| Generic (NonEmptyWordMap a) Source # | |||||
Defined in Data.HashCons.WordMap.Internal Associated Types
Methods from :: NonEmptyWordMap a -> Rep (NonEmptyWordMap a) x # to :: Rep (NonEmptyWordMap a) x -> NonEmptyWordMap a # | |||||
| Show a => Show (NonEmptyWordMap a) Source # | |||||
Defined in Data.HashCons.WordMap.Internal Methods showsPrec :: Int -> NonEmptyWordMap a -> ShowS # show :: NonEmptyWordMap a -> String # showList :: [NonEmptyWordMap a] -> ShowS # | |||||
| Eq a => Eq (NonEmptyWordMap a) Source # | |||||
Defined in Data.HashCons.WordMap.Internal Methods (==) :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool # (/=) :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool # | |||||
| Ord a => Ord (NonEmptyWordMap a) Source # | |||||
Defined in Data.HashCons.WordMap.Internal Methods compare :: NonEmptyWordMap a -> NonEmptyWordMap a -> Ordering # (<) :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool # (<=) :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool # (>) :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool # (>=) :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool # max :: NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a # min :: NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a # | |||||
| Hashable a => Hashable (NonEmptyWordMap a) Source # | |||||
Defined in Data.HashCons.WordMap.Internal | |||||
| type Rep (NonEmptyWordMap a) Source # | |||||
Defined in Data.HashCons.WordMap.Internal type Rep (NonEmptyWordMap a) = D1 ('MetaData "NonEmptyWordMap" "Data.HashCons.WordMap.Internal" "hash-cons-0.2.0.0-inplace" 'False) (C1 ('MetaCons "Leaf" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Word) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "Bin" 'PrefixI 'False) ((S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Word) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Word)) :*: (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (WordMap a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (WordMap a))))) | |||||
singleton :: Hashable a => Word -> a -> WordMap a Source #
O(1). Create a map with a single key-value pair.
singletonNonEmpty :: Hashable a => Word -> a -> NonEmptyWordMap a Source #
O(1). Create a map with a single key-value pair.
insert :: Hashable a => Word -> a -> WordMap a -> WordMap a Source #
O(log n). Insert a key-value pair into the map. If the key is already present, the value is replaced.
insertNonEmpty :: Hashable a => Word -> a -> NonEmptyWordMap a -> NonEmptyWordMap a Source #
lookupNonEmpty :: Word -> NonEmptyWordMap a -> Maybe a Source #
map :: Hashable b => (a -> b) -> WordMap a -> WordMap b Source #
O(n). Map a function over all values in the map.
mapNonEmpty :: Hashable b => (a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b Source #
mapWithKey :: Hashable b => (Word -> a -> b) -> WordMap a -> WordMap b Source #
O(n). Map a function over all key-value pairs in the map.
mapWithKeyNonEmpty :: Hashable b => (Word -> a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b Source #
traverseWithKey :: (Applicative t, Hashable b) => (Word -> a -> t b) -> WordMap a -> t (WordMap b) Source #
O(n). Traverse the map with a function that accesses keys.
traverseWithKeyNonEmpty :: (Applicative t, Hashable b) => (Word -> a -> t b) -> NonEmptyWordMap a -> t (NonEmptyWordMap b) Source #
union :: Hashable a => WordMap a -> WordMap a -> WordMap a Source #
O(n). The union of two maps. If a key occurs in both maps, the value from the left map is used.
unionNonEmpty :: Hashable a => NonEmptyWordMap a -> WordMap a -> NonEmptyWordMap a Source #
unionNonEmptyNonEmpty :: Hashable a => NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a Source #
intersection :: Hashable a => WordMap a -> WordMap a -> WordMap a Source #
O(n). Intersection of two maps. Only keys present in both maps are included.
intersectionNonEmpty :: Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a Source #
difference :: Hashable a => WordMap a -> WordMap a -> WordMap a Source #
O(n). Difference of two maps. Keys in the first map but not in the second are included.
differenceNonEmpty :: Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a Source #
memberNonEmpty :: Word -> NonEmptyWordMap a -> Bool Source #
combine :: Hashable a => Word -> Word -> WordMap a -> WordMap a -> WordMap a Source #
Helper function to combine two subtrees.
join :: Hashable a => Word -> NonEmptyWordMap a -> Word -> NonEmptyWordMap a -> NonEmptyWordMap a Source #
Helper functions.
highestBitMask :: Word -> Word Source #