mono-hash

Hashing for monomorphic containers: FNV-1/FNV-1a, SipHash, and HalfSipHash for any 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:

{-# 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:

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

{-# 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. By design, 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. Bool contributes one byte, 0x00 or 0x01. Float and Double contribute their raw IEEE-754 bit pattern, four or eight bytes most significant first, so 0.0 and -0.0 compare equal yet hash differently. Char contributes UTF-8; a lone surrogate, which String can contain but UTF-8 cannot represent, uses the 3-byte WTF-8 form. String and Text are hashed character by character, while ByteString contributes its raw bytes.

Custom element types

Give the element type a ByteFoldable instance to hash containers of your own type:

{-# LANGUAGE TypeApplications #-}

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.

Because the encoding is untagged (see above), two element types with the same underlying bytes hash alike. An instance can prevent this by folding a tag byte of its own. Here Rgb and Hsl both hold three Word8, yet 0x01 and 0x02 keep their encodings apart:

{-# LANGUAGE TypeApplications #-}

import Data.Hash.Mono.FNV (fnv1a)
import Data.Hash.Mono.Internal.ByteFoldable (ByteFoldable (..))
import Data.Word (Word8, Word64)

data Rgb = Rgb Word8 Word8 Word8

data Hsl = Hsl Word8 Word8 Word8

instance ByteFoldable Rgb where
    foldlBytes f z (Rgb r g b) = f (f (f (f z 0x01) r) g) b

instance ByteFoldable Hsl where
    foldlBytes f z (Hsl h s l) = f (f (f (f z 0x02) h) s) l

fnv1a @Word64 [Rgb 0x12 0x34 0x56]
-- 0x49593a77a021b074

fnv1a @Word64 [Hsl 0x12 0x34 0x56]
-- 0x292dee90a2ab967f

Tags are a convention of the instance and are worth it when distinct types with overlapping byte layouts would otherwise collide, such as values in a sum type or records that share a shape.

Formatting and linting

Sources are formatted with fourmolu and linted with hlint. CI checks both, using the versions pinned in .github/workflows/ci.yml, so run them before opening a pull request:

fourmolu --mode inplace $(git ls-files '*.hs')
hlint src test bench

License

BSD-3-Clause. See LICENSE.