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

1 type
5 values

Packagedata-hash-0.2.0.1
Exports6
LanguageHaskell98
LicenceBSD-3-Clause
SourceRolling.hs

The `RollingHash` type

1 declaration

datadata RollingHash a

Instances1Show

Show (RollingHash a)Defined in data-hash-0.2.0.1 · Data.Hash.Rolling

Construction and manipulation

valuerollingHash :: Int -> RollingHash a

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

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

valuecurrentHash :: RollingHash a -> Hash

valuelastHashes :: RollingHash a -> [Hash]

lastHashes rh returns the last n hashes.

valuewindowSize :: RollingHash a -> Int

The RollingHash type

Construction and manipulation

Querying

The `RollingHash` type