mono-hash-0.1.0.0: README.md
# mono-hash
[](https://hackage.haskell.org/package/mono-hash)
[](https://github.com/phagenlocher/mono-hash/actions/workflows/haskell-ci.yml)
Hashing for monomorphic containers: FNV-1/FNV-1a, SipHash, and HalfSipHash for
any [`MonoFoldable`](https://hackage.haskell.org/package/mono-traversable/docs/Data-MonoTraversable.html#t:MonoFoldable),
including `ByteString`, lazy `ByteString`, `Text`, `String`, and lists of
fixed-width words.
## Motivation
This library hashes data in monomorphic containers irrespective of their
structure. Because only the concatenated element bytes matter, changing the
container while keeping the same bytes leaves the hash unchanged. Below, the
`ByteString` and `Vector Word64` hold exactly the same bytes; each formatted
line of the `ByteString` is one `Word64` in the vector:
```haskell
{-# LANGUAGE NumericUnderscores #-}
{-# LANGUAGE TypeApplications #-}
import qualified Data.ByteString as BS
import qualified Data.Vector as V
import Data.Hash.Mono.SipHash (sipHash)
import Data.Tree (Tree (..))
import Data.WideWord.Word128 (Word128)
import Data.Word (Word32, Word64)
key :: Word128
key = 0x000102030405060708090a0b0c0d0e0f
bytes :: BS.ByteString
bytes =
BS.pack
[ 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77
, 0x88, 0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff
, 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef
]
vector :: V.Vector Word64
vector =
V.fromList
[ 0x00_11_22_33_44_55_66_77
, 0x88_99_aa_bb_cc_dd_ee_ff
, 0x01_23_45_67_89_ab_cd_ef
]
sipHash @Word64 2 4 key bytes
-- 0x6d003ad777121d05
sipHash @Word64 2 4 key vector
-- 0x6d003ad777121d05
```
The same works for any `MonoFoldable`. `Data.Tree.Tree` from `containers`
already has a `MonoFoldable` instance in `mono-traversable`, and it folds in
pre-order:
```haskell
-- Pre-order traversal: the same 24 bytes as six Word32s.
tree :: Tree Word32
tree =
Node
0x00_11_22_33
[ Node 0x44_55_66_77 []
, Node 0x88_99_aa_bb []
, Node 0xcc_dd_ee_ff
[ Node 0x01_23_45_67 []
, Node 0x89_ab_cd_ef []
]
]
sipHash @Word64 2 4 key tree
-- 0x6d003ad777121d05
```
## Usage
```haskell
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TypeApplications #-}
import Data.Hash.Mono.FNV (fnv1a)
import Data.Hash.Mono.HalfSipHash (halfSipHash)
import Data.Hash.Mono.SipHash (sipHash)
import Data.Text (Text)
import Data.WideWord.Word128 (Word128)
import Data.Word (Word32, Word64)
-- FNV-1a with a 64-bit result
fnv1a @Word64 ("hello" :: Text)
-- SipHash-2-4 with a 128-bit key and a 64-bit result
sipHash @Word64 2 4 (0x000102030405060708090a0b0c0d0e0f :: Word128) ("hello" :: Text)
-- HalfSipHash-2-4 with a 64-bit key and a 32-bit result
halfSipHash @Word32 2 4 (0x0001020304050607 :: Word64) ("hello" :: Text)
```
The result type is selected with a type application (or type inference of course):
| Function | Result type |
| -------------- | ---------------------------------------- |
| `fnv1`/`fnv1a` | `Word32`, `Word64`, `Word128`, `Word256` |
| `sipHash` | `Word64`, `Word128` |
| `halfSipHash` | `Word32`, `Word64` |
## Encoding and byte order
Hashing is defined over the concatenation of the elements' byte encodings.
The encoding is not type-tagged, so `[0x01, 0x02 :: Word8]` and
`[0x0102 :: Word16]` hash the same bytes.
`Word8` and `Int8` contribute one byte. Wider integers contribute
their bit pattern most significant byte first; signed integers use two's
complement. `Char` contributes UTF-8; a lone surrogate, which `String` can
contain but UTF-8 cannot represent, uses the 3-byte
[WTF-8](https://wtf-8.codeberg.page) form. `String` and `Text` are
hashed character by character, while `ByteString` contributes its raw bytes.
The library provides instances for `Word8`, `Word16`, `Word32`, `Word64`,
`Word128`, `Word256`, `Int8`, `Int16`, `Int32`, `Int64`, and `Char`.
## Custom element types
Give the element type a `ByteFoldable` instance to hash containers of your
own type:
```haskell
import Data.Hash.Mono.FNV (fnv1a)
import Data.Hash.Mono.Internal.ByteFoldable (ByteFoldable (..))
import Data.Word (Word8, Word64)
data Rgb = Rgb Word8 Word8 Word8
instance ByteFoldable Rgb where
foldlBytes f z (Rgb r g b) = f (f (f z r) g) b
-- Hashes [Rgb 0x12 0x34 0x56] as the bytes 0x12 0x34 0x56.
fnv1a @Word64 [Rgb 0x12 0x34 0x56]
```
The bytes an instance emits are the bytes hashed, so changing an instance
changes every hash of containers holding that element type.
## Formatting and linting
Sources are formatted with [fourmolu](https://github.com/fourmolu/fourmolu) and
linted with [hlint](https://github.com/ndmitchell/hlint). CI checks both, using
the versions pinned in `.github/workflows/ci.yml`, so run them before opening
a pull request:
```console
fourmolu --mode inplace $(git ls-files '*.hs')
hlint src test bench
```
## License
BSD-3-Clause. See [LICENSE](LICENSE).