enumerate-function-0.0.1: simple package for inverting functions and testing totality, via brute enumeration of the domain

Safe HaskellNone
LanguageHaskell2010

Enumerate.Function.Invert

Synopsis

Documentation

fromFunction :: (Enumerable a, Ord a) => (a -> b) -> Map a b Source #

convert a total function to a map.

>>> fromFunction not  -- Prelude not
fromList [(False,True),(True,False)]

fromFunctionM :: (Enumerable a, Ord a) => Partial a b -> Map a b Source #

convert a (safely-)partial function to a map.

wraps reifyFunctionM.

isMapTotal :: (Enumerable a, Ord a) => Map a b -> Bool Source #

does the map contain every key in its domain?

>>> isMapTotal (Map.fromList [(False,True),(True,False)])
True
>>> isMapTotal (Map.fromList [('a',0)])
False

invertMap :: (Ord a, Ord b) => Map a b -> Map b (NonEmpty a) Source #

safely invert any map.

domainM :: Enumerable a => Partial a b -> [a] Source #

the domain of a partial function is the subset of the enumerated input where it's defined.

i.e. when x `member` (domainM f) then fromJust (f x) is defined.

>>> domainM uppercasePartial
['a','b','z']

corange :: Enumerable a => (a -> b) -> [a] Source #

(right name?)

corange _ = enumerated

corangeM :: Enumerable a => Partial a b -> [a] Source #

corangeM _ = enumerated

image :: Enumerable a => (a -> b) -> [b] Source #

the image of a total function.

imageM f = map f enumerated

includes duplicates.

imageM :: Enumerable a => Partial a b -> [b] Source #

the image (not the codomain) of a partial function.

imageM f = mapMaybe f enumerated

includes duplicates.

codomain :: Enumerable b => (a -> b) -> [b] Source #

the codomain of a function. it contains the image.

codomain _ = enumerated

codomainM :: Enumerable b => Partial a b -> [b] Source #

invert :: (Enumerable a, Ord a, Ord b) => (a -> b) -> b -> [a] Source #

invert a total function.

(invert f) b is:

  • [] wherever f is not surjective
  • [y] wherever f is uniquely defined
  • (_:_) wherever f is not injective
invert f = invertM (return.f)

invertM :: (Enumerable a, Ord a, Ord b) => Partial a b -> b -> [a] Source #

invert a partial function.

(invertM f) b is:

  • [] wherever f is partial
  • [] wherever f is not surjective
  • [y] wherever f is uniquely defined
  • (_:_) wherever f is not injective

a Map is stored internally, with as many keys as the image of f.

see also isBijectiveM.

isInjective :: (Enumerable a, Ord a, Ord b) => (a -> b) -> Maybe (b -> Maybe a) Source #

isInjectiveM :: (Enumerable a, Ord a, Ord b) => Partial a b -> Maybe (b -> Maybe a) Source #

returns the inverse of the injection, if injective.

refines (b -> [a]) (i.e. the type of invertM) to (b -> Maybe a).

unlike isBijectiveM, doesn't need an (Enumerable b) constraint. this helps when you want to ensure a function into an infinite type (e.g. show) is injective. and still reasonably efficient, given the (Ord b) constraint.

isUnique :: Ord a => [a] -> Maybe (Set a) Source #

converts the list into a set, if it has no duplicates.

isSurjective :: (Enumerable a, Enumerable b, Ord a, Ord b) => (a -> b) -> Maybe (b -> NonEmpty a) Source #

isSurjectiveM :: (Enumerable a, Enumerable b, Ord a, Ord b) => Partial a b -> Maybe (b -> NonEmpty a) Source #

returns the inverse of the surjection, if surjective. i.e. when a function's codomainM equals its imageM.

refines (b -> [a]) (i.e. the type of invertM) to (b -> NonEmpty a).

can short-circuit.

isBijective :: (Enumerable a, Enumerable b, Ord a, Ord b) => (a -> b) -> Maybe (b -> a) Source #

isBijectiveM :: (Enumerable a, Enumerable b, Ord a, Ord b) => Partial a b -> Maybe (b -> a) Source #

returns the inverse of the bijection, if bijective.

refines (b -> [a]) (i.e. the type of invertM) to (b -> a).

can short-circuit.