
Data.Generics.Fixplate.Util.Hash.Table 




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 worldline), 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 leftbiased, in the sense that
they retain the unique values of the left table (so union t1 t2 belongs to
to t1's worldline, 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 multiparam 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 












Construction and deconstruction









Note that the returned list is ordered by hash, not by keys like Data.Map!





Creates a multiset from a list.


Membership






Insertion / deletion








Union



union == unionWith const



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 leftbiased in the sense that the unique indices from the left hashtable are retained,
while the unique indices from the right hashtable are changed.



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 worldline of the first table.



This one accepts the empty list. The empty imput creates a new worldline.


Intersection



intersection == intersectionWith const








Difference






Unique indices



Look up a unique index, in the form of a (hash,Int) pair, for any key.
If the usersupplied 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).



Keys together with their associated unique values




Produced by Haddock version 2.6.1 