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

Instances

Show (RollingHash a)

Construction and manipulation

rollingHash :: Int -> RollingHash a

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

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

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

currentHash :: RollingHash a -> Hash

lastHashes :: RollingHash a -> [Hash]

lastHashes rh returns the last n hashes.

windowSize :: RollingHash a -> Int