In the last posts we saw some basic abstractions used in functional programming: Eq, Ord, Semigroup and Monoid.
In the next posts we will explore some advanced abstractions that make functional programming even more interesting.
Storically the first advanced abstraction contained in fp-ts is Functor
, but before we can talk about functors we need to learn something about categories since functors are built upon them.
A corner stone of functional programming is composition. But what does that exactely mean? When we can say that two things compose? And when we can say that things compose well?
We need a formal definition of composition. That's what categories are all about.
Categories capture the essence of composition.
Categories
The definition of category is a bit long so I'm going to split its definition in two parts:
- the first is technical (first of all we need to define its constituents)
- the second part will contain what we are most interested in: a notion of composition
Part I (Definition)
A category is a pair (Objects, Morphisms)
where:
-
Objects
is a collection of objects -
Morphisms
is a collection of morphisms (or arrows) between the objects
Note. The term "object" here has nothing to do with OOP, you can think of objects as black boxes you can't inspect, or even as some kind of ancillary placeholders for morphisms.
Each morphism f
has a source object A
and a target object B
where A
and B
are in Objects
.
We write f: A ⟼ B
, and we say "f is a morphism from A to B".
Part II (Composition)
There's an operation ∘
, named "composition", such that the following properties must hold
- (composition of morphisms) whenever
f: A ⟼ B
andg: B ⟼ C
are two morphism inMorphisms
then it must exist a third morphismg ∘ f: A ⟼ C
inMorphisms
which is the composition off
andg
- (associativity) if
f: A ⟼ B
,g: B ⟼ C
andh: C ⟼ D
thenh ∘ (g ∘ f) = (h ∘ g) ∘ f
- (identity) for every object
X
, there exists a morphismidentity: X ⟼ X
called the identity morphism forX
, such that for every morphismf: A ⟼ X
and every morphismg: X ⟼ B
, we haveidentity ∘ f = f
andg ∘ identity
= g.
Example
This category is quite simple, there are only three objects and six morphisms (1A, 1B, 1C are the identity morphisms of A
, B
, C
).
Categories as programming languages
A category can be interpreted as a simplified model of a typed programming language, where:
- objects are types
- morphisms are functions
-
∘
is the usual function composition
The diagram
can be interpreted as a fairly simple, immaginary programming language with only three types and a small bunch of functions.
For example:
A = string
B = number
C = boolean
f = string => number
g = number => boolean
g ∘ f = string => boolean
The implementation could be something like
function f(s: string): number {
return s.length
}
function g(n: number): boolean {
return n > 2
}
// h = g ∘ f
function h(s: string): boolean {
return g(f(s))
}
A category for TypeScript
We can define a category, named TS, as a model for the TypeScript language, where:
-
objects are all the TypeScript types:
string
,number
,Array<string>
, ... -
morphisms are all the TypeScript functions:
(a: A) => B
,(b: B) => C
, ... whereA
,B
,C
, ... are TypeScript types -
identity morphisms are all encoded as a single polymorphic function
const identity = <A>(a: A): A => a
- composition of morphisms is the usual function composition (which is associative)
As a model for TypeScript, TS might seems too limited: no loops, no if
s, almost nothing... Nonetheless this simplified model is rich enough for our main purpose: reason about a well defined notion of composition.
The central problem with composition
In TS we can compose two generic functions f: (a: A) => B
and g: (c: C) => D
as long as B = C
function compose<A, B, C>(g: (b: B) => C, f: (a: A) => B): (a: A) => C {
return a => g(f(a))
}
But what if B != C
? How can we compose such functions? Should we just give up?
In the next post we'll see under which conditions such a composition is possible. We'll talk about functors.
TLDR: functional programming is all about composition
Top comments (1)
I'm really enjoying these posts. Thanks for taking the time