| Safe Haskell | Safe-Infered |
|---|
Data.Generics.Fixplate.Hash
Description
Generic hashing on trees. We recursively compute hashes of all subtrees, giving fast inequality testing, and a fast, but meaningless (more-or-less random) ordering on the set of trees (so that we can put them into Map-s).
The way it works is that when we compute the hash of a node, we use the hashes of the children directly; this way, you can also incrementally build up a hashed tree.
- module Data.Generics.Fixplate.Hash.Class
- data HashAnn hash f a = HashAnn hash (f a)
- getHash :: HashAnn hash f a -> hash
- unHashAnn :: HashAnn hash f a -> f a
- type HashMu hash f = Mu (HashAnn hash f)
- topHash :: HashMu hash f -> hash
- forgetHash :: Functor f => HashMu hash f -> Mu f
- hashTree :: (Foldable f, Functor f, ShowF f, HashValue hash) => Mu f -> HashMu hash f
- hashTreeWith :: (Foldable f, Functor f, HashValue hash) => (f Hole -> hash -> hash) -> Mu f -> HashMu hash f
- hashNode :: (Foldable f, Functor f, ShowF f, HashValue hash) => f (HashMu hash f) -> HashMu hash f
- hashNodeWith :: (Foldable f, Functor f, HashValue hash) => (f Hole -> hash -> hash) -> f (HashMu hash f) -> HashMu hash f
Type classes for different hash functions
Hashed tree type
Hash annotation (question: should the Hash field be strict? everything else in the library is lazy...)
This is custom datatype instead of reusing Ann because of the different Eq/Ord instances we need.
Constructors
| HashAnn hash (f a) |
Instances
| Functor f => Functor (HashAnn hash f) | |
| Foldable f => Foldable (HashAnn hash f) | |
| Traversable f => Traversable (HashAnn hash f) | |
| (Eq hash, ShowF f, Show hash) => ShowF (HashAnn hash f) | |
| (Ord hash, OrdF f) => OrdF (HashAnn hash f) | |
| (Eq hash, EqF f) => EqF (HashAnn hash f) | |
| (Show hash, Show (f a)) => Show (HashAnn hash f a) |
type HashMu hash f = Mu (HashAnn hash f)Source
A tree annotated with hashes of all subtrees. This gives us fast inequality testing,
and fast (but meaningless!) ordering for Map-s.
forgetHash :: Functor f => HashMu hash f -> Mu fSource
Hashing tres
hashTree :: (Foldable f, Functor f, ShowF f, HashValue hash) => Mu f -> HashMu hash fSource
This function uses the ShowF instance to compute
the hash of a node; this way you always have a working
version without writing any additional code.
However, you can also supply your own hash implementation
(which can be more efficient, for example), if you use hashTreeWith instead.
hashTreeWith :: (Foldable f, Functor f, HashValue hash) => (f Hole -> hash -> hash) -> Mu f -> HashMu hash fSource