Copyright | Copyright (c) 1998 Chris Okasaki |
---|---|

License | BSD3; see COPYRIGHT file for terms and conditions |

Maintainer | robdockins AT fastmail DOT fm |

Stability | stable |

Portability | GHC, Hugs (MPTC and FD) |

Safe Haskell | Safe |

Language | Haskell98 |

This module is a central depository of common definitions used throughout Edison.

- class Eq a => Hash a where
- class Hash a => UniqueHash a
- class UniqueHash a => ReversibleHash a where
- class Monoid v => Measured v a | a -> v where
- measure :: a -> v

# Hashing classes

class Eq a => Hash a where Source

This class represents hashable objects. If obeys the following invariant:

forall x,y :: a. (x == y) implies (hash x == hash y)

class Hash a => UniqueHash a Source

This class represents hashable objects where the hash function
is *unique* (injective). There are no new methods, just a
stronger invariant:

forall x,y :: a. (x == y) iff (hash x == hash y)

class UniqueHash a => ReversibleHash a where Source

This class represents hashable objects where the hash is reversible.

forall x :: a. unhash (hash x) == x

Note that:

hash (unhash i) == i

does not necessarily hold because `unhash`

is not necessarily
defined for all `i`

, only for all `i`

in the range of hash.

class Monoid v => Measured v a | a -> v where Source

This class represents a quantity that can be measured. It is
calculated by an associative function with a unit (hence the
`Monoid`

superclass, and by a function which gives the measurement
for an individual item. Some datastructures are able to speed up
the calculation of a measure by caching intermediate values of
the computation.