Homomorphism, and Applicative lesson 10

Applicative lesson 10, homomorphism and composition, is now available.

As I mentioned yesterday, these lessons have taken a lot of work to organize. The turning point for me, what made everything fall together into a coherent story, is realizing that we can view homomorphism as the central concept for all four laws.

What does “homomorphism” mean? Trying to define the word on its own is, I think, easily misleading, because the term is somewhat senseless without mentioning what kind of homomorphism we’re talking about. For example, a monoid homomorphism is a function from one type of monoid to another that respects the monoidal structure; a monoid homomorphism h has to map the identity element of its domain to the identity element in its codomain, and it must be the case that h (x <> y) is equal to h x <> h y (we say that “h preserves the <> operation”). For any kind of algebraic structure, we can talk about homomorphisms for it – semigroup homomorphisms, monoid homomorphisms, semiring homomorphisms, what have you.

One of the Applicative laws states:

That is, it shouldn’t matter whether we lift f and x separately and then apply, or apply f to x and then lift the result. Function application is supposed to work the same way inside a lifted context as it does outside. In other words, “pure preserves function application.”

This is called the “homomorphism law” because it is asserting that pure has to be a homomorphism. This raises the question, then, precisely what kind of homomorphism? What structure and what operations are preserved when pure lifts values into an Applicative context? And as it turns out, each of the four Applicative laws is essential to ensuring that some fundamental property of functions is preserved.

Lesson 10 covers the homomorphism and composition laws. Lesson 11 will address the identity and interchange laws.