Bifunctors

January 2, 2018

This is still an early draft version of the article. Haskell bifunctors, compared to the ubiquitous functors, are much less known while still struturally significant. This article serves as a synthesis and a personal exploration on the topic of usefulness of bifunctors in Haskell.

Without much experience and background, I aim to avoid unwieldy analogies Also known as the monad tutorial fallacy: analogies often fail to generalize. and will paraphrase existing sources in hope of rigor. Bifunctors have served as a nice review to functors and enabled unique applications in datatypes. I wish this article, by no means comprehensive, will eventually convince you the same.

Starting with Functors

See Covariance, contravariance, and positive and negative position for a more comprehensive treatment on the topic of this section.

Haskell functors, intuitively understood as mathematical covariant functors, usually act as the starting point towards the typeclass hierachy. While often leading to applicatives and monads, the somewhat “container-like” route, functors this time start a different path with Contravariant, intuitively mathematical contravariant functors.

class Contravariant f where
	contramap :: (b -> a) -> f a -> f b

As with fmap of functors, parametricityAlso known as free theorems. dictates the uniqueness of contramap for a given ADT. Intuitively, contravariant functors, different from functors, do not contain or produce value, but merely consume value, as seen in instances as wrappers of a -> Bool and a -> b. The chemistry between covariant and contravariant functors might prove intriguing: covariant functors that are also contravariant, bivariant functors, are limited to phantoms containing no value, as evidenced by the coerce functionFor an implementation and a more general context see lens over tea #2. :

coerce :: (Functor f, Contravariant f) => f a -> f b

Curiously all covariant functors and contravariant functors are also invariant functors, defined by invmap . Trivially invmap can be derived from either fmap or contramap.

class Invariant f where
	invmap :: (a -> b) -> (b -> a) -> f a -> f b

Even though ideally we would have class Invariant f => Functor f, in practicality few uses exists for invariant functors to justify that choice.

Towards Bifunctors

The functor instances for tuples might seem unnatural on first sight, as fmap over lists operates on all values but fmap on tuples can only operate on the second element, a fact trivially learned and understood when first approaching the functor typeclass.

Prelude> (+1) <$> [1,2]
[2,3]
Prelude> (+1) <$> (1,2)
(1,3)

The sum type Either also displays similar behavior with regards to its functor instance, with Left values unaffected and Right values changed. Naturally the question of whether a functor instance can be defined with regarding to the first type argument (the type of the first element in tuples, and the type of the left element in sum types) arises, only achievable after introducing wrapper typesAttributed to the lack of type-level lambdas. . The power to apply functions on both positions might also become helpful. In our context of tuples and Either, this motivates a function that can update both values of a tuple at once, and a function that upon meeting a sum type can either operate on the right or the left.

mapTuple :: (a -> x) -> (b -> y) -> (a, b) -> (x, y)
mapEither :: (a -> x) -> (b -> y) -> Either a b -> Either x y

A quick observations yields that with updateTuple given, setting the second argument to id would result in an updater only to the first component of the tuple, while setting the first argument to id degrades the updater to fmap on tuples. The case is similar in updateEither.

The above code, with the kind of (,) and Either both as * -> * -> *, leads to the easy generalization of the core function among bifunctors, bimap, with both tuples and Either as bifunctors.

class Bifunctor p where
	bimap :: (a -> x) -> (b -> y) -> p a b -> p x y

BifunctorsThe bifunctors package includes definitions and common tools for bifunctors discussed here. capture the essence of both of its type arguments as functorial and covariant, suggesting informally both of its type arguments can be used fmap upon simutaneously, as seen in bimap, and individually, as demonstrated by its other functions first and second.

class Bifunctor p where
	first :: (a -> x) -> p a b -> p x b
	second :: (b -> y) -> p a b -> p a y

bimap can be easily derived when having first and second. In the reverse direction, bimap can degrade to first and second trivially. Thus only bimap or both first and second requires definition.

With first and second, a generalized updater to both tuples and Either has been obtained, at least providing some immediate practical use. Wrappers to disguise bifunctors as functors, on either arguments, can be constructed with ease. Likewise, functors, through phantom types, can be lifted to bifunctors.These along with compositions can be found in the bifunctors package.

Before diving deeper into bifunctors, its perhaps more popular counterpart, profunctors, should be mentioned. Profunctors are intuitively mathematical bifunctors that are contravariant in its first type argument while covariant in its second type argumentI still would like to know what bifunctors contravariant on both arguments are called. . Informally a profunctor consumes its first type argument while produces or stores its second argument. Therefore profunctors are occasionally treated as generalized functions.

class Profunctor p where
	dimap :: (x -> a) -> (b -> y) -> p a b -> p x y
	lmap :: (x -> a) -> p a b -> p x b
	rmap :: (b -> y) -> p a b -> p a y

Profunctors, along with profunctor opticsAn overview of which could be found here. , is another awesome topic that requires further exploration. From now on the topic would only focus on the bifunctor typeclass in Haskell.

Laws and Properties

Bifunctor laws are close analogues of functor laws. From fmap id = id bifunctors have:

bimap id id = id
first id = id
second id = id

Nonetheless a unique bifunctor law is also required, tying the three functions together.

bimap f g = first f . second g

If these are ensured, by parametricity, the following laws, similar to the second functor law fmap (g . h) = (fmap g) . (fmap h), hold:

bimap  (f . g) (h . i) = bimap f h . bimap g i
first  (f . g) = first  f . first  g
second (f . g) = second f . second g

Same as functors, by parametricityThe parametricity proof and other derivations of properties can be found in Parametricity for Bifunctors. , for a given ADT only one unique bifunctor instance exists. With these laws a property, symmetric to bimap f g = first f . second g can be derived:

bimap f g = second g . first f

The above property finishes the proof that first and second commutes.

first f . second g = second g . first f

Polynomial Functors and Bifunctors

The algebra of algebraic data types shows that the Bool type can be constructed as a sum of two unit types. Yet how to construct the Maybe type, as denoted in algebra by a + 1, remains unclear. Adding a type parameter, thus allowing passing in variables such as a allows a functorial approach to encode these types. Most covariant functors can be broken down into a small set of primitive type operations using constants, identity, sum and product, constructing datatypes with genericity for free. This can be seen as a crude precursor to generic programming.

data K a x = K a
data I x = I x
data S p q x = L (p x) | R (q x)
data P p q x = P (p x) (q x)

Using K we can encode constants, such as Zero or One lifted into functors.

type Zero = K Void
type One = K ()
type Two = S One One

To retreat into reality, the two inhabitants of Two x, with x fixed, can be constructed.

t :: Two x
t = L (K ())

f :: Two x
f = R (K ())

With the building blocks ready, Maybe can be directly encoded as the sum of identity and 1.

type Maybe = S I One

nothing :: Maybe x
nothing = R (K ())

just :: x -> Maybe x
just x = L (I x)

The representation here might look cumbersome, especially compared to the normal encoding of Maybe, but it does affect our theory and can be mitigated by pattern synonynoms.

Notice that, as the basic building blocks, constant, identity, sum, and product are already functors, the functor instance for the Maybe type as defined above is automatically resolved to be a functor. The functor instances for K, I, S, and P are omitted, as they are straightforward and can be automatically derived by GHC.

A similar approach is taken when recovering Either, to recreate the algebraic form a + b, of two parameters. As more than one parameter determines the type now, the type cannot be encoded using polynomial functors, but instead requires the anagolous polynomial bifunctors.

data K2 a x y = K2 a
data S2 p q x y = L2 (p x y) | R2 (q x y)
data P2 p q x y = P2 (p x y) (q x y)

As the identity I ceases to make sense here, two new bifunctors referencing the first argument and the second are defined.

data Fst x y = Fst x
data Snd x y = Snd y

The polynomial bifunctors here also have uncomplicated instance definitions that are omitted, and can have those derived via the template haskell facilities exported by the bifunctor package. Perhaps unsurprisingly, the polynomial bifunctors have corresponding functor instances.

Either defined as a + b will be encoded as the sum of the first argument and the second, and the constructors prove to be obvious. Notice that the bifunctor and functor instances of Either here will be obtained for free.

type Either = S2 Fst Snd

left :: a -> Either a b
left x = L2 (Fst x)

right :: b -> Either a b
right x = R2 (Snd x)

Fixpoints on Polynomial Functors

To be written.

Fixpoints on Polynomial Bifunctors

To be written.

Bifunctors on Functor Fixpoints

To be written.

Jokers, Clowns, and Dissections

To be written.

Bifunctors - January 2, 2018 - clay harmon