Enumerate.Function.Invert

Documentation

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

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

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

wraps reifyFunctionM.

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

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)

safely invert any map.

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

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]

(right name?)

corange _ = enumerated

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

corangeM _ = enumerated

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

the image of a total function.

imageM f = map f enumerated

includes duplicates.

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

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

imageM f = mapMaybe f enumerated

includes duplicates.

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

the codomain of a function. it contains the image.

codomain _ = enumerated

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

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

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]

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.

getJectivityM :: (Enumerable a, Enumerable b, Ord a, Ord b) => Partial a b -> Maybe Jectivity

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

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

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)

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)

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

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)

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

returns the inverse of the bijection, if bijective.

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

can short-circuit.