WIP DOCUMENT
With category theory it is possible to express many FP (Functional Programming) paradigms, although category theory is defined on a much larger scope than FP.
A category C consists of:
- A class / bunch of objects ob(C).
- A class homab(C) of arrows (morphisms) between these objects.
A category must follow the follwing laws:
- Composibility: ∀ morphisms f: a → b and g: b → c, there must be a composed morphism g ∘ f.
- Identity: ∀ object c ∈ ob(C) there must be and identity (identity morphism) idc: c → c
- Associativity: f ∘ (g ∘ h) == (f ∘ g) ∘ h == f ∘ g ∘ h
To express "things" for a programming language, one can argue on a small category whose objects are types (Int, String, ...).
A small category uses sets as their underlying container for the objects as well as the hom-sets are mathematic sets.
In most programming languages there are product and sum types.
An example of a product type is a tuple (A, B) which is a cartesian produced of type A and B.
This type can be expressed with a universal construction in category theory by defining it in terms of morphisms. In particular, it is expressed by its property to have two projection functions:
(A, B) → Aand(A, B) → BThe product is uniquely defined with this property combined with the fact that all other candidates for a product can be mapped to this pure product.
The unit of a product type is a neutral element. In the case of a pair, it is an empty pair ().
There are also sum types like Either[A, B], which is either of type A or of type B.
The neutral element of this type is Nothing in scala.
As the name might implicit, it is really possible to think of these types as algebraic types.
They are associative (since they are described with category theory), and have a neutral element (sometimes called identity element) and hence, each of them form a Monoid.
Together, these form a Semiring and it is possible to construct and combine them such as you would do with multiplication and addition.
The analogue for the multiplication part are product types, and for the addition part are sum types.
A functor is a mapping that maps objects and other morphisms of one category to another and preservs connections.
Therefore it preserves the structure of a category as well as compositions, e.g. if there in a morphism f: a → b and another morphism g: b → c and hence h = g ∘ f = a → c for a, b, c in category C, it follows that for a functor F it holds that Fh = Fg ∘ Ff = Fa -> Fc.
Furthermore, there must exist an identity which results in a no-op.
In programming, a functor F maps elements of a type A into elements of type B.
But to do so, it operates on some kind of container, like Option[A] or List[A].
These will become Option[B] and List[B] respectively.
def map[A, B](f: A => B): F[A] => F[B]
Since we have these container bound to the functor type and its type constructors to our hand, we say that Option or List is a functor.
These implement the fmap function, or just map in Scala.
So if map is implemented on the type, it is probably a Functor.
Example in Cats
From: https://typelevel.org/cats/typeclasses/functor.html
// Create a trait
trait Functor[F[_]] { // Create trait functor with container F, denoted with F[_]
def map[A, B](fa: F[A])(f: A => B): F[B] // map definition
}
// Example implementation for Option
implicit val functorForOption: Functor[Option] = new Functor[Option] {
def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa match { // map implementation
case None => None
case Some(a) => Some(f(a))
}
}
Analogouesly to functions with two arguments, there are functors that operate on a pair of objects from two categories (not necessarily different ones).
These are called bifunctors.
These are interesting for product and coproduct types which are defined by an cartesian product of two categories.
The corresponding function is called bimap:
def bimap[A, B, C, D](f: A => B)(g: C => D): F[A, C] => F[B, D]
def contramap[A, B](f: A => B): F[B] => F[A]
Contravariant on the first type parameter and covariant on the second type parameter
def dimap
def lmap
def rmap