fixplate-0.1.5: Uniplate-style generic traversals for optionally annotated fixed-point types.Source codeContentsIndex
Data.Generics.Fixplate.Util.Hash.Table
Contents
Construction and deconstruction
Membership
Insertion / deletion
Union
Intersection
Difference
Unique indices
Description

Hash tables, implemented as a structure similar to Map hash (Map key value)].

What this data structure can also give you is a unique value (a (hash,Int) pair) for each key, even during building the table: It is guaranteed to be unique in the past and future lifetime of a single hashtable (that is, one realization of the world-line), among all the keys appearing in that history.

Set operations (union, intersection) clearly break this principle; this is resolved by declaring these operations to be left-biased, in the sense that they retain the unique values of the left table (so union t1 t2 belongs to to t1's world-line, but not to t2's one).

If a key is first removed then added back again, it will get a new value.

To be Haskell98 compatible (no multi-param type classes), when constructing a new hash table, we have to support the function computing (or just fetching, if it is cached) the hash value. This function is then stored in the data type.

Synopsis
data HashTable hash k v
data Bucket k v = Bucket !Int !(Map k (Leaf v))
data Leaf v = Leaf !Int v
getHashValue :: HashTable hash k v -> k -> hash
unHashTable :: HashTable hash k v -> Map hash (Bucket k v)
empty :: (Ord hash, Ord k) => (k -> hash) -> HashTable hash k v
singleton :: (Ord hash, Ord k) => (k -> hash) -> k -> v -> HashTable hash k v
fromList :: (Ord hash, Ord k) => (k -> hash) -> [(k, v)] -> HashTable hash k v
toList :: Ord k => HashTable hash k v -> [(k, v)]
null :: (Ord hash, Ord k) => HashTable hash k v -> Bool
bag :: (Ord hash, Ord k) => (k -> hash) -> [k] -> HashTable hash k Int
lookup :: (Ord hash, Ord k) => k -> HashTable hash k v -> Maybe v
member :: (Ord hash, Ord k) => k -> HashTable hash k v -> Bool
insert :: (Ord hash, Ord k) => k -> v -> HashTable hash k v -> HashTable hash k v
insertWith :: (Ord hash, Ord k) => (a -> v) -> (a -> v -> v) -> k -> a -> HashTable hash k v -> HashTable hash k v
delete :: (Ord hash, Ord k) => k -> HashTable hash k v -> HashTable hash k v
union :: (Ord hash, Ord k) => HashTable hash k a -> HashTable hash k a -> HashTable hash k a
unionWith :: (Ord hash, Ord k) => (v -> v -> v) -> HashTable hash k v -> HashTable hash k v -> HashTable hash k v
unionsWith :: (Ord hash, Ord k) => (v -> v -> v) -> [HashTable hash k v] -> HashTable hash k v
unionsWith' :: (Ord hash, Ord k) => (k -> hash) -> (v -> v -> v) -> [HashTable hash k v] -> HashTable hash k v
intersection :: (Ord hash, Ord k) => HashTable hash k a -> HashTable hash k b -> HashTable hash k a
intersectionWith :: (Ord hash, Ord k) => (a -> b -> c) -> HashTable hash k a -> HashTable hash k b -> HashTable hash k c
intersectionsWith :: (Ord hash, Ord k) => (v -> v -> v) -> [HashTable hash k v] -> HashTable hash k v
intersectionsWith' :: (Ord hash, Ord k) => (k -> hash) -> (v -> v -> v) -> [HashTable hash k v] -> HashTable hash k v
difference :: (Ord hash, Ord k) => HashTable hash k a -> HashTable hash k b -> HashTable hash k a
differenceWith :: (Ord hash, Ord k) => (a -> b -> Maybe a) -> HashTable hash k a -> HashTable hash k b -> HashTable hash k a
getUniqueIndex :: (Ord hash, Ord k) => (hash -> Int -> a) -> k -> HashTable hash k v -> Maybe a
keysWith :: Ord k => (k -> hash -> Int -> a) -> HashTable hash k v -> [a]
mapWithUniqueIndices :: (Ord hash, Ord k) => (hash -> Int -> a -> b) -> HashTable hash k a -> HashTable hash k b
Documentation
data HashTable hash k v Source
data Bucket k v Source
Constructors
Bucket !Int !(Map k (Leaf v))
data Leaf v Source
Constructors
Leaf !Int v
getHashValue :: HashTable hash k v -> k -> hashSource
unHashTable :: HashTable hash k v -> Map hash (Bucket k v)Source
Construction and deconstruction
empty :: (Ord hash, Ord k) => (k -> hash) -> HashTable hash k vSource
singleton :: (Ord hash, Ord k) => (k -> hash) -> k -> v -> HashTable hash k vSource
fromList :: (Ord hash, Ord k) => (k -> hash) -> [(k, v)] -> HashTable hash k vSource
toList :: Ord k => HashTable hash k v -> [(k, v)]Source
Note that the returned list is ordered by hash, not by keys like Data.Map!
null :: (Ord hash, Ord k) => HashTable hash k v -> BoolSource
bag :: (Ord hash, Ord k) => (k -> hash) -> [k] -> HashTable hash k IntSource
Creates a multi-set from a list.
Membership
lookup :: (Ord hash, Ord k) => k -> HashTable hash k v -> Maybe vSource
member :: (Ord hash, Ord k) => k -> HashTable hash k v -> BoolSource
Insertion / deletion
insert :: (Ord hash, Ord k) => k -> v -> HashTable hash k v -> HashTable hash k vSource
insertWith :: (Ord hash, Ord k) => (a -> v) -> (a -> v -> v) -> k -> a -> HashTable hash k v -> HashTable hash k vSource
delete :: (Ord hash, Ord k) => k -> HashTable hash k v -> HashTable hash k vSource
Union
union :: (Ord hash, Ord k) => HashTable hash k a -> HashTable hash k a -> HashTable hash k aSource
 union == unionWith const
unionWith :: (Ord hash, Ord k) => (v -> v -> v) -> HashTable hash k v -> HashTable hash k v -> HashTable hash k vSource

This is unsafe in the sense that the two getHash functions (supplied when the hash tables were created) must agree. The same applies for all the set operations.

It is also left-biased in the sense that the unique indices from the left hashtable are retained, while the unique indices from the right hashtable are changed.

unionsWith :: (Ord hash, Ord k) => (v -> v -> v) -> [HashTable hash k v] -> HashTable hash k vSource
This is unsafe both in the above sense and also that it does not accepts the empty list (for the same reason). The result belongs to the world-line of the first table.
unionsWith' :: (Ord hash, Ord k) => (k -> hash) -> (v -> v -> v) -> [HashTable hash k v] -> HashTable hash k vSource
This one accepts the empty list. The empty imput creates a new world-line.
Intersection
intersection :: (Ord hash, Ord k) => HashTable hash k a -> HashTable hash k b -> HashTable hash k aSource
 intersection == intersectionWith const
intersectionWith :: (Ord hash, Ord k) => (a -> b -> c) -> HashTable hash k a -> HashTable hash k b -> HashTable hash k cSource
intersectionsWith :: (Ord hash, Ord k) => (v -> v -> v) -> [HashTable hash k v] -> HashTable hash k vSource
intersectionsWith' :: (Ord hash, Ord k) => (k -> hash) -> (v -> v -> v) -> [HashTable hash k v] -> HashTable hash k vSource
Difference
difference :: (Ord hash, Ord k) => HashTable hash k a -> HashTable hash k b -> HashTable hash k aSource
differenceWith :: (Ord hash, Ord k) => (a -> b -> Maybe a) -> HashTable hash k a -> HashTable hash k b -> HashTable hash k aSource
Unique indices
getUniqueIndex :: (Ord hash, Ord k) => (hash -> Int -> a) -> k -> HashTable hash k v -> Maybe aSource
Look up a unique index, in the form of a (hash,Int) pair, for any key. If the user-supplied function is injective, then the result is guaranteed to be uniquely associated to the given key in the past and future history of this table (but of course not unique among different future histories).
keysWith :: Ord k => (k -> hash -> Int -> a) -> HashTable hash k v -> [a]Source
Keys together with their associated unique values
mapWithUniqueIndices :: (Ord hash, Ord k) => (hash -> Int -> a -> b) -> HashTable hash k a -> HashTable hash k bSource
Produced by Haddock version 2.6.1