Functors

After a couple of pretty compelling lectures in the topology course I’m taking at school, I’ve found myself on somewhat of a functional programming kick. However, I’ve also been having a really tough time wrapping my mind around functors, profunctors, bifunctors, optics, etc., and I think this is largely because 1) I can’t read Haskell competently, and 2) there are not really many example-based articles on the subject that aren’t either purely mathematical notation or, well, Haskell. Thus, I’ve set out to write up everything I can to help build a foundation for understanding this aspect of functional programming.

Since Python 3 is my go-to language and its new type-hinting system is sufficiently sophisticated to express such ideas, the bulk of my examples will be fully functional snippets. You’ll probably need 3.6+.

Categories

The best place to start is probably with the elementary bits and pieces we use in definitions later on. Categories are one such bit or piece, and I’ll paraphrase Wikipedia for this part. A category is a collection of objects connected by arrows. Arrows can be composed, and each object has an outgoing arrow that points to itself.

A programmatic analog I might choose for categories would be types: int refers to a bunch of objects (well, integers) that have arrows, or relationships with each other. Perhaps these relationships could be arithmetic operations, but it can be more general than that. Types like str, bytes, and user-defined classes can also be thought of as categories.

Morphisms

A morphism is quite simply a mapping from one mathematical structure to another of the same type. Because we love Latin, there are a bunch of named types of morphisms. Thanks, Wolfram.

• A general morphism is called a homomorphism
• A monomorphism is an injective morphism
• An epimorphism is a surjective morphism
• An isomorphism is a bijective morphism

Functors

With that out of the way, what is a functor? It turns out to be pretty symbolically compact! Again, from Wikipedia: given categories \(C, D\), a functor \(F\) from \(C\) to \(D\):

• associates each object \(X \in C\) with an \(F(X) \in D\)
• associates to each morphism \(f: X \mapsto Y\) in \(C\) to \(F(f): F(X) \mapsto F(Y)\) in \(D\) such that:
  • \(\forall X \in C [ F(\text{id}_X) = \text{id}_{F(X)} ]\), noting that \(\text{id}_a(a) = a\)
  • \(\forall f: X \mapsto Y, g: Y \mapsto Z [F(f \circ g) = F(f) \circ F(g)]\), which denotes composition

Certainly concise, but what the hell does this actually mean? Let’s start out with an example of a functor, but first we should go ahead and write out some utility functions.

Foundation

The Pythonic staple of these articles is going to be abc andtyping , the former to indicate abstract types and methods and the latter to give us static type hints and other niceties. We’ll set the stage by putting together some basic types, but first, there are a couple things to note.

• We’re using annotations from __future__ because it allows us to write type hints without using quotes or actually requiring the symbols in the quotes to behave exactly like we say they do. Future annotations will not actually be evaluated during runtime, which is what we want here.
• Throughout this article I’m going to use a class with __call__ whenever I want a proper generic function type hint. Whenever you see that, just know it’s basically equivalent to a generic def.

from __future__ import annotations

import abc
from typing import *
from dataclasses import dataclass

T = TypeVar("T")
C = TypeVar("C", bound="Type")
D = TypeVar("D", bound="Type")
X = TypeVar("X", bound="C")
Y = TypeVar("Y", bound="C")
Z = TypeVar("Z", bound="C")

class Morphism(Generic[X, Y], abc.ABC):
    """A mapping from one object in T to another."""

    def __call__(self, e: X) -> Y:
        """This is the functional implementation of m(x)."""

class Identity(Morphism):
    """A generic identity mapping we'll use for type hinting."""

def identity(x: T) -> T:
    return x

def compose(f: Morphism[X, Y], g: Morphism[Y, Z]) -> Morphism[X, Z]:
    return lambda x: f(g(x))

Some additional notes on what we’re doing here:

• Programmatically, the categories we have to work with are basically subsets of objcects of type Type. In other words, \(C\) and \(D\) are restricted to the meta type.
• All of the example items we use are from C, so we can give them that bound even though Python’s type inference won’t really know what to do with that information.

Functor Typing

With the foundation set, we can start to take a crack at actually drafting our functor. Off the bat, however, you might have noticed that we have a slight ambiguity. As it’s written mathematically, \(F\) serves two purposes: to map \(X \mapsto F(X)\) and to map from \(f \mapsto F(f)\). While that’s fine in theory, in practice this isn’t really feasible as written. We can try our best at inferring the type of an argument passed to F(x: Union[X, f]), but there’s no guarantee that \(X\) and \(f\) are programmatically distinguishable.

To deal with this, I propose that while our mathematical \(F\) implements these two mappings, it’s not necessarily the case that we have to have a single F(x) in our implementation. Instead, we’ll use two seperate parts to handle each mapping. We’ll provide a Functor.Cast[X] which will yield \(F(x)\) and we’ll use __new__ to get. the syntax Functor(f: Morphism[X, Y]), which will yield \(F(f)\).

With that out of the way, let’s go ahead and write out \(F\):

class Functor(Generic[C, D], abc.ABC):
    """A relationship between elements and morphisms in categories."""

    Cast: FunctorCast[C, D]

    @classmethod
    @abc.abstractmethod
    def lift(cls, f: Morphism[X, Y]) -> Morphism[Cast[X], Cast[Y]]:
        """Associate morphisms across the categories."""

    @classmethod
    def map(cls, f: Morphism[X, Y], a: Cast[X]) -> Cast[Y]:
        """Actually apply the lifted morphism on a casted X."""

        return cls.lift(f)(a)

But wait, what’s lift? Well, lift corresponds to the initial operation in \(F(f)\) which yields some function satisfying the same \(F(f) = g: F(X) \mapsto F(Y)\). We would then call \(g(a)\) or Functor.lift(f)(a) with some \(a \in F(X)\), or Functor.Cast[X].

Example and Verification

So to actual write out an example functor, let’s start by choosing our categories. To keep things simple, we’ll first try int as both \(X\) and \(Y\), which both fall into type as \(C\). With regard to \(D\), we can get as specific as Maybe[type], since programmatically that’s the lifted category we’re working in.

@dataclass
class Maybe(Generic[T]):
    value: Optional[T] = None

class MaybeFunctor(Functor):
    """A functor that operates on maybes."""

    Cast = Maybe

    @classmethod
    def lift(cls, f: Morphism[X, Y]) -> Morphism[Cast[X], Cast[Y]]:
        return lambda a: Maybe(f(a.value)) if a.value is not None else a

So, are our constraints for a functor satisfied? Well, let’s take a look, and for the sake of demonstration, \(f\) will simply be the increment function; \(f(x) = x + 1\). We can make the following asserts with no error:

# First part of definition
assert MaybeFunctor.Cast[int] == Maybe[int]

# Second part
f: Morphism[int, int] = lambda x: x + 1
assert MaybeFunctor.map(f, Maybe(1)) == Maybe(2)
assert MaybeFunctor.map(f, Maybe(None)) == Maybe(None)

Let’s also check the two stipulations made by the second line in the definition of the functor:

# F(id_x) = id_Fx
identity_int: Identity[int] = identity
identity_maybe_int: Identity[List[int]] = identity
assert MaybeFunctor.map(identity_int, Maybe(1)) == identity_maybe_int(Maybe(1))

# F(f * g) = F(f) * F(g)
mf = MaybeFunctor
g: Morphism[int, int] = lambda x: x * 2
assert mf.map(compose(f, g), Maybe(1)) == compose(mf.lift(f), mf.lift(g))(Maybe(1))
assert mf.map(compose(f, g), Maybe(None)) == compose(mf.lift(f), mf.lift(g))(Maybe(None))

Extending to Other Types

We can apply functors to more than just single-element box-types like Maybe. Really, we can use functors for anything that can be mapped over - trees, iterables, matrices, etc. For example, let’s take a look at an iterable example. Oh wait, that already exists: Iterable and map! To be formal:

class IterableFunctor(Functor):
    """Formalize how map() and iter() are functors."""

    Cast = Iterable

    @classmethod
    def lift(cls, f: Morphism[Morphism[X, Y]]) -> Morphism[Cast[X], Cast[Y]]:
        return lambda a: map(f, a)

And if you stop for a second and think about it, the usage is almost identical. Take a look (note that we’re using list to unpack and compare the iterators):

assert list(map(f, range(10))) == list(IterableFunctor.map(f, range(10)))

This should also go to show that we don’t necessarily need to have a subclass of Functor to have a “functor” in code. Functors are really just mathematical structures defined by the two rules we mentioned above, and as long as we have analogous components in our languages, we’re using functors. Sure, IterableFunctor is a good way to precisely demonstrate and satisfy these rules, but Iterable and map on their own are perfectly sufficient.

Which is good, because it would be a pain if we had to be so rigorous about everything!

Also keep in mind that we can apply functors to pretty much any data type. An intuitive example might be trees, which a lift would recursively iterate through, or perhaps even a 2D array where we’d use nested functors to map every individual element.