Introduction to Morphisms and Functors
Zaymon Foulds-Cook - April 23, 2019
This article is currently in draft form and will be subject to change over the coming time units.
I am still in the research phase and I have made my best efforts to provide information that is correct, however, there will likely be small mistakes or inaccuracies.
Mathematical jargon is in my opinion the biggest hinderance to FP adoption. Unfortunately the mathematicians got there before programmers when naming abstract concepts.
We can't create new names for things because everyone needs to using a common language. Not having a uniform set of language and definitions would drastically reduce our ability to share of knowledge. However, it's through phrases like "A monad is just a monoid in category of endofunctors" that real programmers keep the gates to all the good that functional programming has to offer.
I'm writing this article to cement my own to understanding about the various key morphisms or functors commonly encountered in functional programming. I hope in doing so I can help demystify some of the esoteric terms you will hear on your journey.
0. Base Morphism
Before jumping into the world of endomorphism's, catamorphism's, functors and more. We need to understand what a regular old morphism is.
In mathematics a morphism is a structure preserving map between two structures.
Let's break down what that means for the programmers among us. If you are familiar with the concept of
Mappable Types then you are already most of the way there to understanding a morphism.
First abstractly we can say that a morphism is the transformation:
A -> B
A morphism is a function which takes a thing of
Type A and converts it into
In computing and category theory a common name for a function that is a morphism is a functor.
- Any mapping function is a morphism if the function maps or transforms from one type to another.
- Functors are morphisms in computation.
Functors are morphisms where the transformation is expressed as a function.
1. Homomorphism | Homofunctor
A homomorphism is a morphism where the transformation preserves the same structure.
What is mathematical structure? A structure in mathematics isn't synonymous with what fields a type has. A structure is a more abstract concept and can denote a few different things. The main two sources of structure we programmers are concerned about are:
- Abstract Algebra
Algebraic structure is the set of all possible operations on a set of some type. Where the collection of operations on that set is the Algebra.
The structure in category theory are categories. Where each category denotes that the type has certain properties, such as: associativity (operations aren't dependent on order) or identity (some element where the product of the thing and the element results in no change).
2. Endomorphism | Endofunctor
Now that we know what a homomorphism is, an endomorphism is much easier to explain. An endomorphism is a homomorphism that maps from a type to itself.
An endomorphism is the transformation:
A -> A
An endofunctor is a function that performs this transformation.
An isomorphism is a morphism that is reversible.
An isomorphism is the transformation:
A -> B | where exists a transformation B -> A
For the transformation to be isomorphic no information can be lost in either direction of the transformation.
Here is an example of a transformation that is not an isomorphism:
["Hello"; " world!"] |> List.fold (+) ""// Results in "Hello world!"
string list is collapsed into a
string we lose information. There is no function that can take the produced
string and definitively calculate the
string list that produced it.
Here is an example of a transformation that is an isomorphism:
[10; 20; 30] |> List.map (fun x -> x * 2)// Results in [20; 40; 60]
Since no information about the structure is lost there exists a function that can perform the reverse transformation:
[20; 40; 60] |> List.map (fun x -> x / 2)// Results in [10; 20; 30]