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.
|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.
|A tree annotated with hashes of all subtrees. This gives us fast inequality testing,
and fast (but meaningless!) ordering for Map-s.
|The hash of the complete tree.
|Interface to the user's hash functions
A concrete hash implementation. We don't use type classes since
- a hash type class does not belong to this library;
- we don't want to restrict the user's design space
Thus we simulate type classes with record types.
|_emptyHash :: hash||the hash of an empty byte sequence
|_hashChar :: Char -> hash -> hash||digest a (unicode) character
|_hashHash :: hash -> hash -> hash||digest a hash value
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.
|Build a hashed node from the children.
|Produced by Haddock version 2.6.1|