invert 1.0.0.2 → 1.0.0.3
raw patch · 4 files changed
+134/−141 lines, 4 filesdep ~basedep ~containersdep ~criterionPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base, containers, criterion, generic-deriving, hashable, unordered-containers, vector
API changes (from Hackage documentation)
Files
- changelog.md +16/−0
- invert.cabal +25/−33
- readme.md +16/−0
- src/Invert.hs +77/−108
+ changelog.md view
@@ -0,0 +1,16 @@+### 1.0.0.3 (2023-01-11)++Packaging and documentation improvement++### 1.0.0.2 (2022-03-15)++- Add support for base 4.16 (ghc 9.2)+- Add support for hashable 1.4++### 1.0.0.1 (2021-06-02)++Minor documentation changes++### 1.0 (2021-02-09)++Initial release
invert.cabal view
@@ -1,31 +1,15 @@ cabal-version: 3.0 name: invert-version: 1.0.0.2+version: 1.0.0.3 synopsis: Automatically generate a function’s inverse category: Functions description: 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.--build-type: Simple+ The function’s domain must be enumerable, and preferably+ rather small. The function’s codomain must belong to the+ @Eq@ class (even better, @Ord@ or @Hashable@). author: Chris Martin maintainer: Chris Martin, Julie Moronuki@@ -36,33 +20,40 @@ license: Apache-2.0 license-file: license.txt +extra-source-files: *.md+ common base default-language: Haskell2010 ghc-options: -Wall build-depends:- base ^>= 4.12 || ^>= 4.13 || ^>= 4.14 || ^>= 4.15 || ^>= 4.16- , containers ^>= 0.6- , hashable ^>= 1.2.7 || ^>= 1.3 || ^>= 1.4- , unordered-containers ^>= 0.2.9- , generic-deriving ^>= 1.14- , vector ^>= 0.12+ , base ^>= 4.14 || ^>= 4.15 || ^>= 4.16 || ^>= 4.17+ , containers ^>= 0.6.4+ , hashable ^>= 1.3.5 || ^>= 1.4+ , unordered-containers ^>= 0.2.17+ , generic-deriving ^>= 1.14.1+ , vector ^>= 0.12.3 || ^>= 0.13 library import: base- exposed-modules: Invert, Invert.Reexport- other-modules: Map, Vector+ exposed-modules:+ Invert+ Invert.Reexport+ other-modules:+ Map+ Vector hs-source-dirs: src default-extensions: NoImplicitPrelude- , NamedFieldPuns- , ExistentialQuantification+ NamedFieldPuns+ ExistentialQuantification test-suite billing-codes-example import: base type: exitcode-stdio-1.0 main-is: billing-codes.hs hs-source-dirs: examples- build-depends: invert+ build-depends:+ , invert benchmark invert-benchmark import: base@@ -71,5 +62,6 @@ hs-source-dirs: benchmarks main-is: bench.hs ghc-options: -O2- build-depends: invert- build-depends: criterion ^>= 1.5+ build-depends:+ , invert+ , criterion ^>= 1.6
+ readme.md view
@@ -0,0 +1,16 @@+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.
src/Invert.hs view
@@ -2,28 +2,22 @@ module Invert (- -- * Overview- -- $overview-- -- * 1. Varieties of function- function, bijection, injection, surjection,+ {- * Overview -} {- $overview -} - -- * 2. Inversion strategies- linearSearchLazy, linearSearchStrict, binarySearch, hashTable,+ {- * 1. Varieties of function -}+ function, bijection, injection, surjection, - -- * 3. Domain enumeration- enumBounded, genum,+ {- * 2. Inversion strategies -} linearSearchLazy,+ linearSearchStrict, binarySearch, hashTable, - -- * The Strategy type- Strategy,- -- $strategyCreation- strategyAll, strategyOneAndAll,+ {- * 3. Domain enumeration -} enumBounded, genum, - -- * Re-exports- -- $reexports- module Invert.Reexport+ {- * The Strategy type -} Strategy, {- $strategyCreation -}+ strategyAll, strategyOneAndAll, - ) where+ {- * Re-exports -} {- $reexports -} module Invert.Reexport,+ )+ where import Invert.Reexport @@ -32,20 +26,20 @@ import qualified Vector -import Data.Eq ( Eq, (==) )-import Data.Foldable ( foldl' )-import Data.Function ( (.) )-import Data.List.NonEmpty ( NonEmpty, nonEmpty )-import Data.Maybe ( Maybe (Just, Nothing), fromMaybe, listToMaybe )-import Data.Ord ( Ord )-import Data.Tuple ( uncurry )-import Prelude ( error )-import Prelude ( Enum, enumFromTo )-import Prelude ( Bounded, minBound, maxBound )+import Data.Eq (Eq, (==))+import Data.Foldable (foldl')+import Data.Function ((.))+import Data.List.NonEmpty (NonEmpty, nonEmpty)+import Data.Maybe (Maybe (Just, Nothing), fromMaybe, listToMaybe)+import Data.Ord (Ord)+import Data.Tuple (uncurry)+import Prelude (error)+import Prelude (Enum, enumFromTo)+import Prelude (Bounded, minBound, maxBound) -import qualified Data.List as List ( lookup, map )-import qualified Data.Maybe as List ( mapMaybe )-import qualified Generics.Deriving as GEnum ( genum )+import qualified Data.List as List (lookup, map)+import qualified Data.Maybe as List (mapMaybe)+import qualified Generics.Deriving as GEnum (genum) {- $overview @@ -94,7 +88,7 @@ of tuples, one for each value of the domain. * 'linearSearchLazy' precomputes nothing at all.- It is possible to use this stategy when the domain is infinite.+ It is possible to use this strategy when the domain is infinite. Our other two strategies, 'binarySearch' and 'hashTable', work by building data structures that allow more efficient lookups.@@ -102,7 +96,7 @@ * 'binarySearch' precomputes a binary search tree; the codomain must belong to the 'Ord' class. - * 'hashTable' precomputers a hash table;+ * 'hashTable' precomputes a hash table; the codomain must belong to the 'Hashable' class. The 'Hashable' class comes from "Data.Hashable" in the @hashable@ package.@@ -124,9 +118,7 @@ The 'Generic' class comes from "GHC.Generics", and the 'GEnum' class comes from "Generics.Deriving" in the @generic-deriving@ package. Both classes are re-exported by "Invert", which you may find convenient-if your primary motivation for deriving 'GEnum' is to invert a function.---}+if your primary motivation for deriving 'GEnum' is to invert a function. -} function :: Strategy a b@@ -177,16 +169,11 @@ surjection (Strategy _ s) as f = finagle . s (inverseEntries as f) where finagle = fromMaybe (error "Not a surjection!") . nonEmpty -{- |-- 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.---}+{-| 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 = Strategy ([(b, a)] -> b -> Maybe a)@@ -194,13 +181,11 @@ {- $strategyCreation - === Defining your own strategies-- If you want to design your own strategy instead- of using one provided by this module, use either- 'strategyAll' or 'strategyOneAndAll'.+=== Defining your own strategies --}+If you want to design your own strategy instead+of using one provided by this module, use either+'strategyAll' or 'strategyOneAndAll'. -} strategyAll :: ([(b, a)] -> b -> [a]) -- ^ Find all matches@@ -224,29 +209,20 @@ f Map{ Map.empty, Map.singleton, Map.union, Map.lookup } = lookup . foldl' union empty . List.map (uncurry singleton) -{- |-- A function inversion strategy that precomputes nothing at all.- It is possible to use this stategy when the domain is infinite.---}+{-| A function inversion strategy that precomputes nothing at all +It is possible to use this strategy when the domain is infinite. -} linearSearchLazy :: Eq b => Strategy a b linearSearchLazy = Strategy one all where one bas b = List.lookup b bas all bas b = List.mapMaybe (sndIfFstEq b) bas -{- |-- 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.---}+{-| A function inversion 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 linearSearchStrict = strategyAll f where@@ -257,59 +233,53 @@ sndIfFstEq :: Eq b => b -> (b, a) -> Maybe a sndIfFstEq x (b, a) = if b == x then Just a else Nothing -{- |-- 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.---}+{-| 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 binarySearch = mapStrategy Map.ordSingleMap Map.ordMultiMap -{- |-- 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.---}+{-| 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 hashTable = mapStrategy Map.hashSingleMap Map.hashMultiMap --- |--- '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)---+{-| A convenient way to enumerate the domain for a function that you+want to invert, using the 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] enumBounded = enumFromTo minBound maxBound --- |--- '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---+{-| Use GHC generics to enumerate a function's domain +This 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] genum = GEnum.genum @@ -322,6 +292,5 @@ List of re-exports: - __'Hashable'__ (for the 'hashTable' inversion strategy)- - __'Generic'__ and __'GEnum'__ (for the 'genum' domain enumeration approach)---}+ - __'Generic'__ and __'GEnum'__ (for the 'genum' domain+ enumeration approach) -}