-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Automatically generate a function's inverse
--
-- This library deals with computing a function's inverse. This is, of
-- course, not possible in general, so the applicability of this library
-- comes with some caveats:
--
--
-- - The function's domain must be enumerable, and preferably rather
-- small. We provide a few suggestions and utilities for how to enumerate
-- the domain.
-- - The function's codomain must belong to the Eq class. An
-- Ord or Hashable instance is also nice, to
-- accommodate a data structure for efficient lookups.
-- - The functions for inverting injections, surjections, and
-- bijections require some care to use correctly, because the library
-- does not verify these properties.
--
--
-- The main purpose of this library is to provide documentation and
-- convenience. It does not contain a great quantity of code, so a user
-- hesitant to incur a dependency on the package might well choose only
-- to read and borrow its techniques.
@package invert
@version 1.0
module Invert.Reexport
-- | The class of types that can be converted to a hash value.
--
-- Minimal implementation: hashWithSalt.
class Hashable a
-- | Representable types of kind *. This class is derivable in GHC
-- with the DeriveGeneric flag on.
--
-- A Generic instance must satisfy the following laws:
--
--
-- from . to ≡ id
-- to . from ≡ id
--
class Generic a
class GEnum a
module Invert
function :: Strategy a b -> [a] -> (a -> b) -> b -> [a]
bijection :: Strategy a b -> [a] -> (a -> b) -> b -> a
injection :: Strategy a b -> [a] -> (a -> b) -> b -> Maybe a
surjection :: Strategy a b -> [a] -> (a -> b) -> b -> NonEmpty a
-- | A function inversion strategy that precomputes nothing at all. It is
-- possible to use this stategy when the domain is infinite.
linearSearchLazy :: Eq b => Strategy a b
-- | A function inversation strategy that works by precomputing a strict
-- sequence of tuples, one for each value of the domain.
--
-- For larger functions, it may be preferable to use binarySearch
-- or hashTable instead to get a more efficient inverse.
linearSearchStrict :: Eq b => Strategy a b
-- | A function inversion strategy that works by precomputing a binary
-- search tree. The data structure imposes the requirement that the
-- codomain belongs to the Ord class.
binarySearch :: Ord b => Strategy a b
-- | A function inversion strategy that works by precomputing a hash table.
-- The data structure imposes the requirement that the codomain belongs
-- to the Hashable class.
hashTable :: (Eq b, Hashable b) => Strategy a b
-- | enumBounded can be a convenient way to enumerate the domain for
-- a function that you want to invert. It uses two stock-derivable
-- classes, Enum and Bounded.
--
-- To derive the required typeclass instances, add the following deriving
-- clause to the type's definition:
--
--
-- deriving (Enum, Bounded)
--
enumBounded :: (Enum a, Bounded a) => [a]
-- | genum uses GHC generics; it requires deriving Generic
-- and GEnum. The Generic class comes from
-- GHC.Generics, and the GEnum class comes from
-- Generics.Deriving in the generic-deriving package.
--
-- To derive the required typeclass instances, enable the following
-- language extensions:
--
--
-- {-# language DeriveGeneric, DeriveAnyClass, DerivingStrategies #-}
--
--
-- Then add the following deriving clauses to the type's definition:
--
--
-- deriving stock Generic
-- deriving anyclass GEnum
--
genum :: GEnum a => [a]
-- | An inversion strategy is an approach for producing the inverse of an
-- (a -> b) function.
--
-- All strategies produce the same results, but they have operational
-- differences that affect performance.
data Strategy a b
strategyAll :: ([(b, a)] -> b -> [a]) -> Strategy a b
strategyOneAndAll :: ([(b, a)] -> b -> Maybe a) -> ([(b, a)] -> b -> [a]) -> Strategy a b