License | BSD-style |
---|---|

Maintainer | jcpetruzza@gmail.com |

Stability | experimental |

Portability | portable |

Safe Haskell | None |

Language | Haskell98 |

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)

- data RollingHash a
- rollingHash :: Int -> RollingHash a
- addAndRoll :: Hashable a => RollingHash a -> a -> RollingHash a
- currentHash :: RollingHash a -> Hash
- lastHashes :: RollingHash a -> [Hash]
- windowSize :: RollingHash a -> Int

# The `RollingHash`

type

data RollingHash a Source

Show (RollingHash a) |

## Construction and manipulation

rollingHash :: Int -> RollingHash a Source

`rollingHash n`

creates a `RollingHash`

of window
size `n`

(for `n > 0`

)

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

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

lastHashes :: RollingHash a -> [Hash] Source

`lastHashes rh`

returns the last `n`

hashes.

windowSize :: RollingHash a -> Int Source