data-hash-0.2.0.0: Combinators for building fast hashing functions.

Portabilityportable
Stabilityexperimental
Maintainerjcpetruzza@gmail.com
Safe HaskellSafe-Infered

Data.Hash.Rolling

Contents

Description

Efficient implementation of a rolling hash, i.e., the computation of a hash through a moving window of a fixed size n over some stream. All operations are O(1) (in particular, they do not depend on the size of the window).

Some laws that this type satisfies:

  • currentHash rh == foldl1 combine (lastHashes rh)
  • length (lastHashes rh) <= windowSize rh
  • length (lastHashes $ addAndRoll rh a) == windowSize rh -- whenever length (lastHashes rh) == windowSize rh
  • last (lastHashes $ addAndRoll rh x) == hash a
  • init (lastHashes $ addAndRoll rh a) isSuffixOf (lastHashes rh)

Synopsis

The RollingHash type

data RollingHash a Source

Instances

Construction and manipulation

rollingHash :: Int -> RollingHash aSource

rollingHash n creates a RollingHash of window size n (for n > 0)

addAndRoll :: Hashable a => RollingHash a -> a -> RollingHash aSource

addAndRoll x rh adds a new input element and rolls the window one place through the input (if at least n elements were already consumed).

Querying

lastHashes :: RollingHash a -> [Hash]Source

lastHashes rh returns the last n hashes.