Instances1Show
Show (RollingHash a)Defined in data-hash-0.2.0.1 · Data.Hash.Rolling
Moduledata-hash-0.2.0.1Haskell98
Data.Hash.Rolling
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 rhlength (lastHashes $ addAndRoll rh a) == windowSize rh -- whenever length (lastHashes rh) == windowSize rhlast (lastHashes $ addAndRoll rh x) == hash ainit (lastHashes $ addAndRoll rh a)isSuffixOf(lastHashes rh)
Synopsis
- data RollingHash
- value rollingHash
- value addAndRoll
- value currentHash
- value lastHashes
- value windowSize
- Packagedata-hash-0.2.0.1
- Exports6
- LanguageHaskell98
- LicenceBSD-3-Clause
- SourceRolling.hs
The RollingHash type
Construction and manipulation
rollingHash n creates a RollingHash of window
size n (for n > 0)
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 rh returns the last n hashes.