    {-# LANGUAGE Safe #-}

    ------------------------------------------------------------------------
    -- |
    -- Module      :  Data.Hashable.Lifted
    -- Copyright   :  (c) Milan Straka 2010
    --                (c) Johan Tibell 2011
    --                (c) Bryan O'Sullivan 2011, 2012
    -- SPDX-License-Identifier : BSD-3-Clause
    -- Maintainer  :  johan.tibell@gmail.com
    -- Stability   :  provisional
    -- Portability :  portable
    --
    -- Lifting of the 'Hashable' class to unary and binary type constructors.
    -- These classes are needed to express the constraints on arguments of
    -- types that are parameterized by type constructors. Fixed-point data
    -- types and monad transformers are such types.

    module Data.Hashable.Lifted
        ( -- * Type Classes
          Hashable1(..)
        , Hashable2(..)
          -- * Auxiliary Functions
        , hashWithSalt1
        , hashWithSalt2
        , defaultLiftHashWithSalt
          -- * Motivation
          -- $motivation
        ) where

    import Data.Hashable.Class

    -- $motivation
    --
    -- This type classes provided in this module are used to express constraints
    -- on type constructors in a Haskell98-compatible fashion. As an example, consider
    -- the following two types (Note that these instances are not actually provided
    -- because @hashable@ does not have @transformers@ or @free@ as a dependency):
    --
    -- > newtype WriterT w m a = WriterT { runWriterT :: m (a, w) }
    -- > data Free f a = Pure a | Free (f (Free f a))
    --
    -- The 'Hashable1' instances for @WriterT@ and @Free@ could be written as:
    --
    -- > instance (Hashable w, Hashable1 m) => Hashable1 (WriterT w m) where
    -- >     liftHashWithSalt h s (WriterT m) =
    -- >         liftHashWithSalt (liftHashWithSalt2 h hashWithSalt) s m
    -- > instance Hashable1 f => Hashable1 (Free f) where
    -- >     liftHashWithSalt h = go where
    -- >         go s x = case x of
    -- >             Pure a -> h s a
    -- >             Free p -> liftHashWithSalt go s p
    --
    -- The 'Hashable' instances for these types can be trivially recovered with
    -- 'hashWithSalt1':
    --
    -- > instance (Hashable w, Hashable1 m, Hashable a) => Hashable (WriterT w m a) where
    -- >     hashWithSalt = hashWithSalt1
    -- > instance (Hashable1 f, Hashable a) => Hashable (Free f a) where
    -- >     hashWithSalt = hashWithSalt1

    --
    -- $discussion
    --
    -- Regardless of whether 'hashWithSalt1' is used to provide an implementation
    -- of 'hashWithSalt', they should produce the same hash when called with
    -- the same arguments. This is the only law that 'Hashable1' and 'Hashable2'
    -- are expected to follow.
    --
    -- The typeclasses in this module only provide lifting for 'hashWithSalt', not
    -- for 'hash'. This is because such liftings cannot be defined in a way that
    -- would satisfy the @liftHash@ variant of the above law. As an illustration
    -- of the problem we run into, let us assume that 'Hashable1' were
    -- given a 'liftHash' method:
    --
    -- > class Hashable1 t where
    -- >     liftHash :: (a -> Int) -> t a -> Int
    -- >     liftHashWithSalt :: (Int -> a -> Int) -> Int -> t a -> Int
    --
    -- Even for a type as simple as 'Maybe', the problem manifests itself. The
    -- 'Hashable' instance for 'Maybe' is:
    --
    -- > distinguisher :: Int
    -- > distinguisher = ...
    -- >
    -- > instance Hashable a => Hashable (Maybe a) where
    -- >     hash Nothing = 0
    -- >     hash (Just a) = distinguisher `hashWithSalt` a
    -- >     hashWithSalt s Nothing = ...
    -- >     hashWithSalt s (Just a) = ...
    --
    -- The implementation of 'hash' calls 'hashWithSalt' on @a@. The hypothetical
    -- @liftHash@ defined earlier only accepts an argument that corresponds to
    -- the implementation of 'hash' for @a@. Consequently, this formulation of
    -- @liftHash@ would not provide a way to match the current behavior of 'hash'
    -- for 'Maybe'. This problem gets worse when 'Either' and @[]@ are considered.
    -- The solution adopted in this library is to omit @liftHash@ entirely.