data-hash- Combinators for building fast hashing functions.

Safe HaskellSafe-Infered




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)


The RollingHash type

data RollingHash a Source


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).


lastHashes :: RollingHash a -> [Hash]Source

lastHashes rh returns the last n hashes.