Data.Enumerate.Map

converting between partial functions and maps.

-- doctest

>>> :set +m
>>> :set -XLambdaCase
>>> :{
let uppercasePartial :: (MonadThrow m) => Char -> m Char  -- Partial Char Char 
    uppercasePartial = \case
     'a' -> return 'A'
     'b' -> return 'B'
     'z' -> return 'Z'
     _   -> failed "uppercasePartial"
:}

a (safely-)partial function is isomorphic with a Map:

fromFunctionM . toFunctionM = id 
toFunctionM . fromFunctionM = id

modulo the error thrown.

Documentation

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

convert a total function to a map.

>>> fromFunction 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.

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

convert a map to a function, if the map is total.

>>> let Just not' = toFunction (Map.fromList [(False,True),(True,False)])
>>> not' False 
True 

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

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

lookup failures are throwMn as a PatternMatchFail.

>>> let idPartial = toFunctionM (Map.fromList [(True,True)])
>>> idPartial True
True
>>> idPartial False 
*** Exception: toFunctionM

unsafeToFunction :: Ord a => Map a b -> a -> b

wraps lookup

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.

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

refines the partial function, if total.

>>> :{
let myNotM :: Monad m => Bool -> m Bool
    myNotM False = return True 
    myNotM True  = return False 
:} 
>>> let Just myNot = isTotalM myNotM
>>> myNot False
True

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.