DEV Community: Menestret Martin

Anatomy of semigroups and monoids

Menestret Martin — Thu, 21 Feb 2019 10:24:52 +0000

[Check my articles on my blog here]

I will try to group here, in an anatomy atlas, basic notions of functional programming that I find myself explaining often lately into a series of articles.

The idea here is to have a place to point people needing explanations and to increase my own understanding of these subjects by trying to explain them the best I can.
I'll try to focus more on making the reader feel an intuition, a feeling about the concepts rather than on the perfect, strict correctness of my explanations.

Part 1: Anatomy of functional programming
Part 2: Anatomy of an algebra
Part 3: Anatomy of a type class
Part 4: Anatomy of semi groups and monoids
Part 5: Anatomy of functors and category theory
Part 6: Anatomy of the tagless final encoding - Yet to come !

What is a semigroup ?

General definition

Semigroup (and monoid, you'll see later) is a complicated word for a really simple concept.
We'll cover quickly semigroups and we'll explain longer monoids since they are strongly related.

Wikipedia's definition is:

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

Ok, that sounds a bit abstract, let's try to re-phrase it with programming terms:

In the context of programming, a semigroup is composed of two things:

A type A
An associative operation combining two values of type A into a value of type A, let's call it combine
- That would be a function with a type signature: (A, A) => A
- Which is associative, meaning that the order in which you combine elements together (where you decide to put your parenthesis) does not matter
  - combine(combine(a1, a2), a3) == combine(a1, combine(a2, a3)) with a1, a2, a3 values of type A

Then it is said that A forms a semigroup under combine.

Some examples

Integer under addition

type: Int
operation: +

Indeed,

+ type here is: (Int, Int) => Int
+ is associative (20 + 20) + 2 == 20 + (20 + 2)

Integers form a semigroup under addition.

Boolean under OR

type: Boolean
operation: ||

Indeed,

|| type here is: (Boolean, Boolean) => Boolean
|| is associative (true || false) || true == true || (false || true)

Booleans form a semigroup under OR.

List under list concatenation

type: List[A]
operation: ++

Indeed,

++ type here is: (List[A], List[A]) => List[A]
++ is associative (List(1, 2) ++ List(3, 4)) ++ List(5, 6) == List(1, 2) ++ (List(3, 4) ++ List(5, 6))

More examples !

Integers under multiplication
Booleans under AND
String under concatenation
A LOT more.

We'll now explore monoids since they are a "upgraded" version of semigroups.

What is a monoid ?

General definition

Given the definition of a semigroup, the definition of a monoid is pretty straight forward:

In mathematics, a monoid is an algebraic structure consisting of a set together with an associative binary operation and an identity element.

Which means that a monoid is a semigroup plus an identity element.

In our programming terms:

In the context of programming, a monoid is composed of two things:

A semigroup:
- A type A
- An associative operation combining two values of type A into a value of type A, let's call it combine
An identity element of type A, let's call it id, that has to obey the following laws:
- combine(a, id) == a with a a value of type A
- combine(id, a) == a with a a value of type A

Then it is said that A forms a monoid under combine with identity element id.

Some examples

We could take our semigroups examples here and add their respective identity elements:

Integer under addition
- With identity element 0:
  - 42 + 0 = 42
  - 0 + 42 = 42
Boolean under OR
- With identity element false:
  - true || false == true, false || true == true
  - false || false == false
List under list concatenation
- With identity element Nil (empty List):
  - List(1, 2, 3) ++ Nil == List(1, 2, 3)
  - Nil ++ List(1, 2, 3) == List(1, 2, 3)

Whenever you have an identity element for your semigroup's type and combine operation that holds the identity laws, then you have a monoid for it.

But be careful, there are some semigroups which are not monoids:

Tuples form a semigroup under first (which gives back the tuple's first element).

type: Tuple2[A, A]
operation: first (def first[A](t: Tuple2[A, A]): A = t._1)

Indeed,

first type here is: Tuple2[A, A] => A
first is associative first(Tuple2(first(Tuple2(a1, a2)), a3)) == first(Tuple2(a1, first(Tuple2(a2, a3)))) with a1, a2, a3 values of type A

But there is no way to provide an identity element id of type A so that:

first(Tuple2(id, a)) == a and first(Tuple2(a, id)) == a with a a value of type A

What the hell is it for ?

Monoid is a functional programming constructs that embodies the notion of combining "things" together, often in order to reduce "things" into one "thing". Given that the combining operation is associative, it can be parallelized.

And that's a BIG deal.

As a simple illustration, this is what you can do, absolutely fearlessly when you know your type A forms a monoid under combine with identity id:

You have a huge, large, massive list of As that you want to reduce into a single A
You have a cluster of N nodes and a master node
You split your huge, large, massive list of As in N sub lists
You distribute each sub list to a node of your cluster
Each node reduce its own sub list by combining its elements 2 by 2 down to 1 final element
They send back their results to the master node
The master node only has N intermediary results to combine down (in the same order as the sub lists these intermediary results were produced from, remember, associativity !) to a final result

You successfully, without any fear of messing things up, parallelized, almost for free, a reduction process on a huge list thanks to monoids.

Does it sound familiar ? That's naively how fork-join operations works on Spark ! Thank you monoids !

How can we encode them in Scala ?

Semigroups and monoids are encoded as type classes.

We are gonna go through a simple implementation example, you should never have to do it by hand like that since everything we'll do is provided by awesome FP libraries like Cats or Scalaz.

Here are our two type classes:

trait Semigroup[S] {
    def combine(s1: S, s2: S): S
}

trait Monoid[M] extends Semigroup[M] {
    val id: M
}

And here is my business domain modeling:

type ItemId = Int
case class Sale(items: List[ItemId], totalPrice: Double)

I want to be able to combine all my year's sales into one big, consolidated, sale.

Let's define a monoid type class instance for Sale by defining:

id being an empty Sale which contains no item ids, and 0 as totalPrice
combine as concatenation of item id lists and addition of totalPrices

implicit val saleMonoid: Monoid[Sale] = new Monoid[Sale] {
    override val id: Sale                          = Sale(List.empty[ItemId], 0)
    override def combine(s1: Sale, s2: Sale): Sale = Sale(s1.items ++ s2.items, s1.totalPrice + s2.totalPrice)
}

Then I can use a lot of existing tooling, generic functions, leveraging the fact that the types they are working on are instances of monoid.

combineAll (which is also provided by Cats or Scalaz) is one of them and permit to, generically, combine all my sales together for free !

def combineAll[A](as: List[A])(implicit M: Monoid[A]): A = {
    def accumulate(accumulator: A, remaining: List[A]): A = remaining match {
        case Nil          ⇒ accumulator
        case head :: tail ⇒ accumulate(M.combine(accumulator, head), tail)
    }
    accumulate(M.id, as)
}

val sales2018: List[Sale] = List(Sale(List(0), 32), Sale(List(1), 10))
val totalSale: Sale       = combineAll(sales2018) // Sale(List(0, 1),42)

Nota bene: Here, for sake of simplicity, I did not implement combineAll with foldLeft so I don't have to explain foldLeft, but you should know that my accumulate inner function is foldLeft and that combineAll should in fact be implemented like that:

def combineAll[A](as: List[A])(implicit M: Monoid[A]): A = as.foldLeft(M.id)(M.combine)

Voilà !

More material

If you want to keep diving deeper, some interesting stuff can be found on my FP resources list and in particular:

Scala with Cats - Semigroup and monoid chapters
Why Spark can’t foldLeft: Monoids and Associativity
Cats documentation
Let me know if you need more

Conclusion

To sum up, we saw:

How simple semigroups and monoids are and how closely related they are
We saw examples of semigroups and monoids
We had an insight about how useful these FP constructs can be in real life
And finally we showed how they are encoded in Scala and had a glimpse on what you can do with it thanks to major FP librairies

I'll try to keep that blog post updated.
If there are any additions, imprecision or mistakes that I should correct or if you need more explanations, feel free to contact me on Twitter or by mail !

Anatomy of an algebra

Menestret Martin — Thu, 21 Feb 2019 10:16:37 +0000

[Check my articles on my blog here]

I will try to group here, in an anatomy atlas, basic notions of functional programming that I find myself explaining often lately into a series of articles.

Part 1: Anatomy of functional programming
Part 2: Anatomy of an algebra
Part 3: Anatomy of a type class
Part 4: Anatomy of semi groups and monoids
Part 5: Anatomy of functors and category theory
Part 6: Anatomy of the tagless final encoding - Yet to come !

What is an algebra ?

Functional programmers tend to talk a lot about algebras, so a good starting point would be to understand what an algebra is.
A simple definition would be (from Wikipedia):

In its most general form, an algebra is the study of mathematical symbols and the rules for manipulating these symbols

Then to rephrase it in simpler terms, it is a system formed by:

Symbols, items or "things"
Operations on thoses "things"
Properties and rules about those operations

A simple algebra example would be:

Symbols: the integer numbers
Operations: addition and multiplication
Properties and rules:
- Closure: the result of the two operations is itself in integer number
- Associativity: a + (b + c) = (a + b) + c and a × (b × c) = (a × b) × c
- Commutativity: a + b = b + a and a × b = b × a
- Identity elements: a + 0 = a and a * 1 = a
- And so on (check the link if you want to see the rest)

How does it relates to FP ?

Domain modeling

When modeling a business domain, in functional programming, we separate strongly data from behaviors (see the Data/behavior relationship section).

To do that:

We create types on one side
Pure functions manipulating those types
And these functions have to respect some strict business logic

Doesn't that ring any bell ?

We manipulate algebras !

Symbols: our business types
Operations: our business functions acting on those types
Properties and rules: our business logic implemented in these functions, and our property based tests
- We won't cover those here, but to give you an idea, these are not unit tests, but tests based on function properties that they must always verify (such as: "A combination of several sales cannot result in a negative price") while tested against a wide range of more or less random values generated by a test framework

A concrete example

To make it clearer, let's take a dummy example.

Say we have to produce sales reports, we would probably model our domain like:

type Amount = Int
type Price = Int

final class ID(val value: Int) extends AnyVal
final case class Item(id: ID, price: Price)
final case class Sales(items: List[(ID, Amount)], totalPrice: Price)

trait SalesOperations {
    def combineAll(sales: List[Sales]): Sales
    def generateReport(sales: Sales): String
}

In that case:

Symbols: Amount, Price, ID, Item, Sales, etc. (our business types)
Operations: combineAll, generateReport (operations on those types)
Properties and rules: the business logic and the tests we haven't implemented here

That's pretty much it !

It happens frequently to have shared behaviors that are common to several types.
We want to be able to design functions that can be run on those different types and have the expected behavior depending on their input types. Those functions are said then said to be polymorphic.

That's a problem we solve with type classes.

What is an ADT ?

ADT stands for algebraic data type. Well, we talked a bit about algebras but we didn't talk about types yet.

What is a type ?

A type or a data type, is just a classification of data, a set of values or inhabitants, that we use to tell the compiler how we intend to use data so it can check that we respect the rules (that's the type checking).

Boolean is a type that classifies these two values: true, false
String is a type that reprents an infinity of inhabitants, all the possible characters combinations
Option[A] is a type that represents all the values of type A (wrapped in a Some) + the value None
- Option has a number of inhabitants equals to the number of inhabitants of the type A + 1 (the None value)
- Option[Boolean] has 3 inhabitants: Some(true), Some(false), None
Unit is a type that has only 1 inhabitant, the value: ()
Noting is a type that has no member (there is no way to create a value whose type is Nothing)

What is an algebraic data type then ?

Here is Wikipedia's definition of an algebraic data type:

In computer programming, especially functional programming and type theory, an algebraic data type is a kind of composite type, i.e., a type formed by combining other types.

We call these new types ADTs because we create them by combining existing types... well, guess what ? We use an algebra again !

This is algebra is the following:

Symbols: existing types: primitive types, other existing ADTs, ... (Sales, Boolean, String, Int, ...)
Operations: sum and product (we'll see what they mean)
Properties and rules: some properties and laws about these sum and product operations (we'll also see what they mean)

Sum

sum is the action of combining by "summing" their respective values together.

You can see it as a way to define that: values of a sum type can only be either a value of this OR that type (the OR is the key intuition here).

It is done, in Scala, usually by using:

sealed traits and their instances as case classes or case objects

Or less often:

The Either[A, B] type

That way, when you declare:

sealed trait CoinSide
case object Heads extends CoinSide
case object Tails extends CoinSide

You are creating an ADT CoinSide which is a sum type (created with a sum operation) which has two and only two possible values (or inhabitants), Heads or Tails.

The same would be achieved with:

type CoinSide = Either[Heads, Tails]

Whose possible values would then be, Left(Heads) or Right(Tails).

These are just two different encodings for the same thing.

Sum properties

The sum operation also have properties.

I won't go into full details here but (these examples would equally be true with sealed traits + their implementations instead of Either type):

The number of values of a sum type is the sum of the values of its composing types members (just as you would assume for addition on integers)
- Boolean has two inhabitants: true and false
- Either[Boolean, Boolean] which is a sum type of two types Boolean has four inhabitants:
  - Left(true)
  - Left(false)
  - Right(true)
  - Right(false)
- Either[Boolean, Either[Boolean, Boolean]]] is a sum type between a Boolean and another sum type of a Boolean and a Boolean
  - Well guess what ? It has 2 + (2 + 2) values !
It has an identity element which is the Nothing type which has no values at all
- Either[Boolean, Nothing] is a sum type of a Boolean with the sum identity. Because there is no way to create a value of type Nothing, it does not exist, so there is no way to construct a Right, it has only two values:
  - Left(true)
  - Left(false)
It is associative, Either[Boolean, Either[Boolean, Boolean]]] is the same as Either[Either[Boolean, Boolean]],Boolean], you can enumerate the values, you'll see (well isomorphic, we have the same "expressive power" with both representations, but let's say they are the same) !
And so on (I'll give you more material at the end if you want to keep diving)

Product

product is the action of combining two or more types together by "multiplying" their respective values together.

You can see it as a way to define that values of a product type are the combination of values of this AND that type (the AND is the key intuition here).

It is done, in Scala usually by using:

case classes

Or less often

tuples

That way, when you declare:

case class TwoCoinsAndABoolean(fst: CoinSide, snd: CoinSide, b: Boolean)
// or
type TwoCoinsAndABoolean = (CoinSide, CoinSide, Boolean)

These are just two different encodings for the same thing.

You are creating an ADT TwoCoinsAndABoolean which is a product types (created with a product operation) which has the number of values of its members multiplied.

In our case 8 values (2 * 2 * 2):

TwoCoinsAndABoolean(Heads, Heads, true) or (Heads, Heads, true)
TwoCoinsAndABoolean(Heads, Tails, true) or (Heads, Tails, true)
TwoCoinsAndABoolean(Tails, Heads, true) or (Tails, Heads, true)
TwoCoinsAndABoolean(Tails, Tails, true) or (Tails, Tails, true)
TwoCoinsAndABoolean(Heads, Heads, false) or (Heads, Heads, false)
TwoCoinsAndABoolean(Heads, Tails, false) or (Heads, Tails, false)
TwoCoinsAndABoolean(Tails, Heads, false) or (Tails, Heads, false)
TwoCoinsAndABoolean(Tails, Tails, false) or (Tails, Tails, false)

You can observe that product types values are the cartesian product of their composing types values !

Product properties

The product operation also have properties.

I won't go into full details here but (these example would equally be true with case classes instead of tuples):

The number of values of a product types is the product of the number of the values of its combining members (as you would assume for multiplication on integers)
- Boolean has two inhabitants: true and false
- (Boolean, Boolean) which is a product type of two types Boolean has four values:
  - (true, true)
  - (true, false)
  - (false, true)
  - (false, false)
- (Boolean, (Boolean, Boolean) is a product type between a Boolean and another product type of a Boolean and a Boolean
  - Well guess what ? It has 2 * (2 * 2) values !
It has an identity which is the famous Unit type which has only one inhabitant, the value ()
- (Boolean, Unit) is a product type of a Boolean with the product identity. It has two values:
  - (true, ())
  - (false, ())
It is associative, (Boolean, (Boolean, Boolean) is the same as ((Boolean, Boolean),Boolean), you can enumerate the values, you'll see (well isomorphic, we have the same "expressive power" with both representations, but let's say they are the same) !
And so on (I'll give you more material at the end if you want to keep diving)

Mixed types

Of course, as we saw in some of the examples, ADTs can be combinations of other ADTs, such as sum of products, products of sums, product of products and so on.

More material

If you want to keep diving deeper, some interesting stuff can be found on my FP resources list and in particular:

Functional and Reactive Domain Modeling (An awesome book about functional domain modeling using algebras)
Kinds of types in Scala
Why do Functional Programmers always talk about Algebra(s)?

Conclusion

All that long digression was only meant to show you that, creating new composite data types the way we do in pure FP is done by using an algebra.

That's why these composite types are called Algebraic Data Types :).

To sum up, we learnt:

What was an algebra
How algebras were used to model domains in a neat way and how it was adequate to the pure functional programming approach
What was a type
How creating new data types was done by using an algebra composed by types and operations on them and thus why the types created that were called algebraic data types

I'll try to keep that blog post updated.
If there are any additions, imprecision or mistakes that I should correct or if you need more explanations, feel free to contact me on Twitter or by mail !

Anatomy of a type class

Menestret Martin — Thu, 21 Feb 2019 10:12:12 +0000

[Check my articles on my blog here]

I will try to group here, in an anatomy atlas, basic notions of functional programming that I find myself explaining often lately into a series of articles.

Part 1: Anatomy of functional programming
Part 2: Anatomy of an algebra
Part 3: Anatomy of a type class
Part 4: Anatomy of semi groups and monoids
Part 5: Anatomy of functors and category theory
Part 6: Anatomy of the tagless final encoding - Yet to come !

Motivation

Data / behavior relationship

OOP and FP have two different approaches when it comes to data/behavior relationship:

Object oriented programming often combines data and behavior by mixing them into classes that:
- Store data as an internal state
- Expose methods that act on it and may mutate it
Functional programming aims to completely separate data from behavior by:
- Defining types (ADT on one side that expose no behavior and only holds data
- Functions taking values of some of these types as inputs, acting on them and outputting values of some of those types (leaving the input values unchanged)

You can check Anatomy of functional programming for examples.

Polymorphism

The general idea of polymorphism is to increase code re-use by using a more generic code.

The are several kinds of polymorphisms but the one adressed by type classes is ad hoc polymorphism, so we are going to focus on that one.

Ad hoc polymorphism is defined on Wikipedia by:

Ad hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types, because a polymorphic function can denote a number of distinct and potentially heterogeneous implementations depending on the type of argument(s) to which it is applied

It is a mechanism allowing a function to be defined in such a way that the actual function behavior that is going to depends on the types of the parameters over which it is applied to.

To make it clearer, Ad hoc polymorphism avoids you from having to define printInt, printDouble, printString functions, a print function is enough.

Our print will rely on ad hoc polymorphism to behave differently based on the type of the the parameter they are applied to.

The purpose of that is mainly to program by manipulating interfaces (as a concept, the layer allowing elements to communicate, not as in a Java Interface even their purpose is to encode that concept) exposing shared, common, behaviors or properties and use these behaviors instead of writing different function implementations for each of the concrete types abstracted by these interfaces.

Your print function might somehow require a Printable interface, abstracting for its argument the ability to print themselves.

Object oriented programming often use interface subtyping to permit polymorphism by making concrete classes inherit interfaces exposing the needed shared behaviors
Functionnal programming, willing to strongly separate data and behavior favours type classes which allows to add behaviors to existing types without having to modify them or having to plan they will need these functionnalities beforehand.

What's a type class ?

A type class can be described literally as a class of types, a grouping of types, that shares common capabilities.

It represents an abstraction of something that a grouping of types would have in common, just as "Things that can say Hi" abstracts over every concrete types that have the ability to greet or as "Things that have petals" might abstract over flowers in the real world.

It plays the same role as an interface in OOP but it is more than that:

It allows to add behavior to existing types (even type that are out of our codebase scope)
It permits conditionnal interfacing, by that I mean, we can encode that A is a member of the type class T1 if A is also a member of type class T2

How can it be done in Scala ?

Type classes are not specific to Scala and can be found in many functional programming languages.
They are not a first class construct in Scala, as it can be in Haskell but it still can be done quit easily.

In Scala it is encoded by:

A trait which exposes the "contract" of the type class, what the type class is going to abstract over,
The concrete implementations of that trait for every types that we want to be instances of that type classes.

Our type class for "types that can say Hi" is going to be:

trait CanGreet[T] {
    def sayHi(t: T): String
}

Representing all the types T which have the capability to sayHi.

Given a:

case class Player(nickname: String, level: Int)
val geekocephale = Player("Geekocephale", 42)

We now create a Player instance of the CanGreet trait for it to be an instance of our type class.

val playerGreeter: CanGreet[Player] = new CanGreet[Player] {
    def sayHi(t: Player): String = s"Hi, I'm player ${t.nickname}, I'm lvl ${t.level} !"
}

Thanks to what we did, we can now define generic functions such as:

def greet[T](t: T, greeter: CanGreet[T]): String = greeter.sayHi(t)

greet is polymorphic in the sense that it will work on any T as long as it gets an instance of CanGreet for that type.

greet(geekocephale, playerGreeter)

However, that is a bit cumbersome to use, and we can leverage Scala's implicits power to make our life easier (and to get closer to what's done in other languages' type class machinery).

Let's redifine our greet function, and make our CanGreet instance implicit as well.

Some hygiene guidelines comming from Haskell type classes:

Make your type class instances live
- Either in the type class companion object
- Or in the type's companion object of your type T, here Player
Have no more than one instance per type for a given type class (especially true in Scala)

Type class and type companion objects are nice places for type class instances because both of their scopes are checked when a function requires an implicit of type TC[T] where TC is your type class trait and T is the type for which you look for a type class instance.

object Player {
    implicit val playerGreeter: CanGreet[Player] = new CanGreet[Player] {
        def sayHi(t: Player): String = s"Hi, I'm player ${t.nickname}, I'm lvl ${t.level} !"
    }
}

def greet[T](t: T)(implicit greeter: CanGreet[T]): String = greeter.sayHi(t)

Now, we can call our greet function without explicitly passing the CanGreet instance as long as we have an implicit instance for the type T we are using in scope (which we have, playerGreeter) !

greet(geekocephale)

To sum up, here's all the code that we wrote so far:

trait CanGreet[T] {
    def sayHi(t: T): String
}

case class Player(nickname: String, level: Int)

object Player {
    implicit val playerGreeter: CanGreet[Player] = new CanGreet[Player] {
        def sayHi(t: Player): String = s"Hi, I'm player ${t.nickname}, I'm lvl ${t.level} !"
    }
}

def greet[T](t: T)(implicit greeter: CanGreet[T]): String = greeter.sayHi(t)

Optionnal cosmetics

That part is absolutely not mandatory to understand how type classes work, it is just about common syntax additions to what we saw before, mostly for convenience, and it can be skipped to go directly to conclusion.

def greet[T](t: T)(implicit greeter: CanGreet[T]): String

Is strictly the same thing and can be refactored as:

def greet[T: CanGreet](t: T): String

The function signature looks nicer, and I think it expresses better the "need" for T to "be" an instance of CanGreet, but there is a drawback: we lost the possibility to refer to our CanGreet implicit instance by a name.
To do so, in order to summon our instance from the implicit scope, we can use the implicitly function:

def greet[T: CanGreet](t: T): String = {
    val greeter: CanGreet[T] = implicitly[CanGreet[T]]
    greeter.sayHi(t)
}

To make it less cumbersome, you'll commonly see a companion object for type classes traits with an apply method:

object CanGreet {
    def apply[T](implicit C: CanGreet[T]): CanGreet[T] = C
}

It does exactly what we did in our last greet function implementation, allowing us to now re-write our greet function as follows:

def greet[T: CanGreet](t: T): String = CanGreet[T].sayHi(t)

CanGreet[T] is calling the companion object apply function (CanGreet[T] is in fact desugarized as CanGreet.apply[T]() with the implicit instance in scope passed to apply) to summon T's CanGreet instance from implicit scope and we can immediately use it in our greet function by calling .sayHi(t) on it.

Finally, you'll also probably see implicit classes, called syntax for our type class that holds the operation our type class permits:

implicit class CanGreetSyntax[T: CanGreet](t: T) {
    def greet: String = CanGreet[T].sayHi(t)
}

Allowing our greet function to be called in a more convenient, OOP method way:

geekocephale.greet

To sum up, here's all the code we wrote with these upgrades:

trait CanGreet[T] {
    def sayHi(t: T): String
}

object CanGreet {
    def apply[T](implicit C: CanGreet[T]): CanGreet[T] = C
}

implicit class CanGreetSyntax[T: CanGreet](t: T) {
    def greet: String = CanGreet[T].sayHi(t)
}

case class Player(nickname: String, level: Int)

object Player {
    implicit val playerGreeter: CanGreet[Player] = new CanGreet[Player] {
        def sayHi(t: Player): String = s"Hi, I'm player ${t.nickname}, I'm lvl ${t.level} !"
    }
}

Type classes bonus

A posteriori subtyping

Type classes have more to offer than classical OOP subtyping.

Type classes permit to add behavior to existing types (including types that are not yours):

import java.net.URL

implicit val urlGreeter: CanGreet[URL] = new CanGreet[URL] {
    override def sayHi(t: URL): String = s"Hi, I'm an URL pointing at ${t.getPath}"
}

We just added to java.net.URL the property of being able to say Hi !

Conditionnal interfacing

You can define conditionnal type class instances:

implicit def listGreeter[A: CanGreet]: CanGreet[List[A]] = new CanGreet[List[A]] {
    override def sayHi(t: List[A]): String = s"Hi, I'm an List : [${t.map(CanGreet[A].sayHi).mkString(",")}]"
}

By requiring [A: CanGreet], we just stated that List[A] in an instance of the CanGreet type class if and only if A is an instance of CanGreet.

Just to show you that we can push that conditional behavior further, we could have done something complety useless like:

implicit def listGreeter[A: CanGreet: MySndTypeClass](implicit c: MyThirdTypeClass[String]): CanGreet[List[A]] = ???

Here we request, for List[A] to be an instance of CanGreet, that:

A is instance of
- CanGreet
- MySndTypeClass
String is an instance of MyThirdTypeClass (which is, I have to admit, absolutly stupid).

Tooling

Simulacrum is an awesome library that helps tremendously reducing the boilerplate by using annotations that will generate the type classe and syntax stuff for you at compile time
Magnolia is a great library as well to automaticly derive your type classes instances

We did not talk about type classes derivation which is a bit more advanced topic, but the basic idea being that, if your types A and B are instances of a type class, and if you have a type C formed by combining A and B, such as:

case class C(a: A, b: B)

sealed trait C
case class A() extends C
case class B() extends C

It makes the type C automatically an instance of your type class !

More material

If you want to keep diving deeper, some interesting stuff can be found on my FP resources list and in particular:

Conclusion

So to conclude here, we saw why type classes are useful, what they are, how they are encoded in Scala and some cosmetics and tooling that might help you to work with them.

We went through:

How to create a class of types that provides shared behaviors
- Without having to know it beforehand (we don't extend our types nor modify them)
- Without having to mix that behavior to the data (the case class itself)
How to create new instances of our type class
How to leverage polymorphism by designing polymorphic functions defined and working for any type T as long as an (implicit) instance of it's required type class is provided !

I'll try to keep that blog post updated.
If there are any additions, imprecision or mistakes that I should correct or if you need more explanations, feel free to contact me on Twitter or by mail !

Edit: Thanks Jules Ivanic for the review :).

Anatomy of functional programming

Menestret Martin — Thu, 21 Feb 2019 10:05:48 +0000

[Check my articles on my blog here]

I will try to group here, in an anatomy atlas, basic notions of functional programming that I find myself explaining often lately into a series of articles.

Part 1: Anatomy of functional programming
Part 2: Anatomy of an algebra
Part 3: Anatomy of a type class
Part 4: Anatomy of semi groups and monoids
Part 5: Anatomy of functors and category theory
Part 6: Anatomy of the tagless final encoding - Yet to come !

What is functional programming ?

A general definition

To begin our anatomy atlas of functional programming, the first question would be: what is functional programming ?

I would define it that way:

A style of programming which aims to avoid side effects by using, as much as possible, pure functions that manipulate immutable data.

As much as possible, here, means everywhere except, if needed, in your main function.

That way, almost your entire code base is said to be "pure" and has the nice properties we'll see after.

Your main is the only "impure" part but you drastically reduced the portion of your code you have to be extra careful with.

The definition we gave for functional programming introduced the notions of side effects, pure functions and immutable data that we are going to explain.

A general purpose of functional programming would be to reduce, as much as possible, the moving parts of your software.

Side effects

A function should have only one effect: the effect of computing its return value.

Any other effects triggered by that function are side effects (logging, printing, inputs and outputs of any kinds, and so on).

Functional programming does not forbid to do IO or logging, but it encourages to do it explicitly rather than in secret, hidden in functions, without publicly declaring it.

Pure functions

Pure functions are somehow a computational analogy of mathematical function.

Purity rules

Pure functions have to respect a set of simple rules:

Determinism: pure functions will always return the same output when given the same inputs. Consequently, they cannot use non-local variables, global mutable states, perform IO, and so on
- def add(a: Int, b: Int): Int = a + b is deterministic, it will always return the same output value when given the same input values
- def rand(a: Int): Int = Random.nextInt(a) is not, each call may return different values
- A function returning Unit should be a huge code smell, as it is does nothing else than side effecting (execept if it only returns Unit and nothing else, but I doubt you would want to do that...) ! It a determinism's nemesis !
Totality: pure functions from type A => B (A is called the domain and B the co-domain), have to be defined for every value of its domain, here for every value of type A
- def divide(a: Int, b: Int): Int = a / b is not total, it will crash if b == 0
- def safeDivide(a: Int, b: Int): Option[Int] = Try(a / b).toOption is total by handling undefined case with None
Referential transparency: pure functions calls should be replacable by their results anywhere they are used without altering the rest of the program

    def launchTheMissiles: Unit = ???
    def formattingMyStuff(s: String): String = {
        launchTheMissiles
        s.toUpperCase
    }

Here we cannot replace any calls to formattingMyStuff("hi") by "HI" without altering the rest of the program, because formattingMyStuff performs a side effect, launchTheMissiles. We know that by replacing formattingMyStuff("hi") by "HI", the missiles won't be launched.

With def purelyFormattingMyStuff(s: String): String = s.toUpperCase howerver, any call to it could be replaced directly by the uppercased argument and we know that the program would work the same way it did before.

To go even further, a referentialy transparent function should be replaceable by a lookup table associating directly its inputs to its output.

Since def boolToString(b: Boolean): String = if (b) "That's true !" else "That's wrong..." is referencially transparent, it is replaceable by the following lookup table without altering the rest program:

Input	Output
`true`	"That's true !"
`false`	"That's wrong..."

Now you can tell how functions that respect those rules limit the moving parts of your software.

They do what their signatures tell they do, and they only do that. They don't move other stuff around.

How to do "real world" stuff then ?

You tell me that the one and only function effect should only be to allocate memory and to use some processor power to compute its result ? And nothing else ?

Without the ability to do IO, to encode randomness or to fail, it might be pretty hard to do any real world work...

Of course, functional programming lets you do all that but it asks you do to it explicitly.

Here are some examples:

A function returning an Option[Int] is in fact just returning an Int but it adds explicitly to that Int the effect of being able to fail by wrapping it in an Option
A function returning an Either[String, Int] is in fact just returning an Int but it adds explicitly to that it the effect of potentialy returning a String instead (which is often used to describe a failure with its reason), by wrapping it in an Either[String, Int]
A Task[Int] or IO[Int] (these are more or less the same thing), returns a computation that is not run yet but that will produce an Int or fail, when executed, which is often used to explicitly represent a value that is obtained by doing an IO. It is the description of the things to do to produce that Int, but it hasn't started yet.
A lot of other effects can be encoded that way but going in details is some other blog post material (you can find a lot of related resources here)

Data philosophy

Data / behavior relationship

OOP and FP have two different approaches when it comes to data/behavior relationship:

Object oriented programming often combines data and behavior by mixing them into classes that:
- Store data as an internal state
- Expose methods that act on it and may mutate it

case class Player(nickname: String, var level: Int) {
    def levelUp(): Unit          = { level = level + 1 }
    def sayHi(): String          = s"Hi, I'm player $nickname, I'm lvl $level !"
}

Functional programming aims to completely separate data from behavior by:
- Defining types (ADT on one side that expose no behavior and only holds data
- Functions taking values of some of these types as inputs, acting on them and outputting values of some of those types (leaving the input values unchanged)

case class Player(nickname: String, level: Int)

object PlayerOperations {
    def levelUp(p: Player): Player = p.copy(level = p.level + 1)
    def sayHi(p: Player): String   = s"Hi, I'm player ${p.nickname}, I'm lvl ${p.level} !"
}

Expression problem

The expression problem is about how a language behaves when it comes to add to an existing code base:

New cases to existing types
New behaviors (functions) over existing types

And if they manage to do that without having to modify the existing code.

The idea behind the expression problem is to compare how languages and programming paradigms tackle these problems.

OOP and FP have both a different answer to that problem.

Object oriented programming paradigm

👍 : Adding new cases to an existing data type
- A new class extending the existing class / interface
👎 : Adding a new behavior over an existing data type
- A new method on the appropriate super class / interface which impacts every single sub classes

Base case:

trait MyType { def behavior: String }

final case class A() extends MyType { override def behavior: String = "I'm A" }
final case class B() extends MyType { override def behavior: String = "I'm B" }

Adding a new case to an existing data type:

final case class C() extends MyType { override def behavior: String = "I'm C" }

Adding a new behavior over an existing data type:

trait MyType { 
    def behavior: String
    def newBehavior: String
}

Now you have to get back to every single classes extending MyType to implement newBehavior.

Functional programming paradigm

👎 : Adding new cases to an existing data type
- A new type to your existing sum type (cf: Anatomy of an algebra which impacts every functions over that data type (you'll have to handle that new case)
👍 : Adding a new behavior over an existing data type
- A new function, nothing more

Base case:

sealed trait MyType
final case class A() extends MyType
final case class B() extends MyType

def behavior(m: MyType): String = m match {
    case A() ⇒ "I'm A"
    case B() ⇒ "I'm B"
}

Adding a new case to an existing data type:

final case class C() extends MyType

Now you have to get back to every functions over MyType to pattern match on the new case.

Adding a new behavior over an existing data type:

def newBehavior(m: MyType): String = m match {
    case A() ⇒ ???
    case B() ⇒ ???
  }

Immutable Data

That one is simple: a value is said to be immutable if, once evaluated, there is no way to change it.

That is mutability, and thus, should be avoided in functional programming:

var meaningOfLife = 41
meaningOfLife = meaningOfLife + 1

That piece of data is immutable:

val meaningOfLife = 42
meaningOfLife = meaningOfLife + 0
//<console>:12: error: reassignment to val
//       meaningOfLife = meaningOfLife + 0

If you really have to use mutability, say for performance reasons, I encourage you to do it with caution, by isolating and encapsulating the mutation in an immutable construct such as:

val magic = {
    var mutableMagic = 0
    mutableMagic = 42
    mutableMagic
}

That way you know that mutability won't spread and your moving part is contained in a non moving one.

Benefits of FP

For now, what we saw about FP was more or less only constraints.

But functional programming shouldn't be only seen a set of constraints, as Runar Bjarnason would say, constraints buy you a lot of freedom.

That may not seem obvious but I'll try to explain why.

Equationnal reasoning

Pure functions, while being restrictive allow you to reason about your program in a way that would not be possible otherwise, it is called equational reasoning.

It means that, once you figure out that f(x) = something, then everywhere f(x) appears, you can simply replace it by something and keep reducing your problematic complexity thay way as far as you need.

Equationnal reasoning allows you to follow the logic of your program by replacing your function calls by their results, exactly how you'd do when trying to solve a mathematical equation:

If you had these two equations:

    2x - 3y  = 12
    y + 2x   = 180

Then you could isolate x the first one:

    2x - 3y = 12
    2x      = 12 + 3y
    x       = (12 + 3y ) / 2

And then simply replace x in the rest of your reasoning by its value:

    y + 2x                  = 180
    y + 2 * (12 + 3y) / 2   = 180
    y + 12 + 3y             = 180
    4y                      = 168
    y                       = 42

That's a powerful way to reason about complex problems.

Without pure functions, you would have to analyze every single function calls, check if those functions do anything more than returning their results, keep a mental track of that other things they do, and keep analyzing while trying not to forget what you just witnessed.

That's a good example about how constraints on one side give you a lot of freedom on other sides.

Predictable data

As your data is immutable, it is easier to keep track of its state, since its state doesn't change.
The only way to create data is by using its constructor (in a broad sense) and that, also, reduces a lot your software's moving parts.

You know for sure that, when using a piece of data, it has not been modified in the meantime by something else, you can rely on it.

If you isolate the places where changes occur by severely restricting mutation, you create a much smaller space for errors to occur and have fewer places to test.
(Neal Ford)

Morever, it gives you thread safety by design, your data will never be in an unknown or undesirable state, which is huge in our more and more concurrent applications.

Playing with Lego

In addition to equational reasoning and immutability, I'll try to show you what else FP brings to you your code with an analogy.

Do you remember how it was to play with Lego ? Well FP lets you play with functions the way you did with Lego pieces.

You had plenty of pieces that do or don't fit together, each pieces being solid, immutable, and doing one single, simple thing.

Just as pure functions do.

It gives you:

Trivial refactoring
- You know that you can change this red brick by that blue one if it respects the same contract without affecting at all the rest of your construct for obscure reasons (side effects, mutability, ...)
Composability
- You can build a construct on one side, another on the other side and plug them together to make a new, more complex, construct safely that behaves as you would expect
- That's exactly what you'll do with your pure functions, you know they take inputs, compute and return outputs and nothing else, thus you can safely compose them and build up more and more complexity fearlessly
Easier testability
- You can easily test if a piece does what it is expected to since it does nothing more than being, well, a simple, independent, side effect free, piece !

Crystallizing design patterns

To end with FP benefits, there is this curious thing called Curry–Howard correspondence which is a direct analogy between mathematical concepts and computational calculus (which is what we do, programmers).

This correspondence means that a lot of useful stuff discovered and proven for decades in Math can then be transposed to programming, opening a way for a lot of extremely robust constructs for free.

In OOP, Design patterns are used a lot and could be defined as idiomatic ways to solve a given problems, in specific contexts but their existences won't save you from having to apply and write them again and again each time you encounter the problems they solve.

Functional programming constructs, some directly coming from category theory (mathematics), solve directly what you would have tried to solve with design patterns.

The classical functional programming toolbox gives you constructs to handle, almost for free:

Global states
Concurrency
Computation parallelization
Computation failure
Validation accumulation
Asynchronism
Sequentiallity
...

You can find here a list of how FP constructs corresponds to OOP classical design patterns: Lambda, the ultimate pattern factory.

Pretty convenient !

More material

If you want to keep diving deeper, some interesting stuff can be found on my FP resources list and in particular:

Conclusion

To sum up, we saw:

What actually is functional programming and that is what about manipulating immutable data with pure functions
Then we saw what were side effects, pure functions and immutability
The liberties that FP constraints gives you (equationnal reasoning, predictability, composability, easier refactoring, easier testability, etc.)
That it exists a bridge between the world of Mathematical logic and computation and how that bridge is used to give us powerful constructs
How some of these constructs can address real world problems you would have solved with cumbersome, hand crafted, design patterns otherwise

I'll try to keep that blog post updated.
If there are any additions, imprecision or mistakes that I should correct or if you need more explanations, feel free to contact me on Twitter or by mail !

Anatomy of functors and category theory

Menestret Martin — Thu, 21 Feb 2019 08:51:28 +0000

[Check my articles on my blog here]

I will try to group here, in an anatomy atlas, basic notions of functional programming that I find myself explaining often lately into a series of articles.

Part 1: Anatomy of functional programming
Part 2: Anatomy of an algebra
Part 3: Anatomy of a type class
Part 4: Anatomy of semi groups and monoids
Part 5: Anatomy of functors and category theory
Part 6: Anatomy of the tagless final encoding - Yet to come !

What is a functor ?

There's a nice answer by Bartosz Milewski on Quora from which I'll keep some parts:

I like to think of a functor as a generalization of a container. A regular container contains zero or more values of some type. A functor may or may not contain a value or values of some type (...) .

So what can you do with such a container? You might think that, at the minimum, you should be able to retrieve values. But each container has its own interface for accessing values. If you try to specify that interface, you're Balkanizing containers. You're splitting them into stacks, queues, smart pointers, futures, etc. So value retrieval is too specific.

It turns out that the most general way of interacting with a container is by modifying its contents using a function.

Let's try to rephrase that

Functors represent containers
For now, we won't care about their particularities, all we need to know is that, at some point, they will maybe hold a value or values "inside" (but keep in mind that every container have particularities, I'll refer to that at the end)
Defining an generic interface about how to access values inside a container does not make any sense since some containers' values would be accessed by index (arrays for example), others only by taking the first element (stacks for example), other by taking the value only if it exists (optionals), etc.
However, we can define an interface defining how the value(s) inside containers is modified by a function despite being in a container

So, to summarize, a functor is a kind of container that can be mapped over by a function.

But functors have to respect some rules, called functor's laws...

Identity: A functor mapped over by the identity function (the function returning its parameter unchanged) is the same as the original functor (the container and its content remain unchanged)
Composition: A functor mapped over the composition of two functions is the same as the functor mapped over the first function and then mapped over the second one

A quick note about functor / container parallel: the analogy is convenient to get the intuition, but not all functors will not fit into that model, keep it in a corner of you mind so that you're not taken off guard.

How does it look like in practice

Along the next sections, the examples and code snippets I'll provide will be in Scala.

Let explore some examples

We're going to play with concrete containers of Int values to try to grasp the concept.

val halve: Int => Float = x => x.toFloat / 2

Here we defined the function from Int to Float that we are going to use to map over our containers

Our first guinea pig is Option[Int], which is a container of (0 or 1) Int.

val intOpt: Option[Int] = Some(99)
val mappedResult1: Option[Float] = intOpt.map(halve)

We can see that an Option[Int] turns into an Option[Float], the inner value of the container being modified from Int to Float when mapped over with a function from Int to Float...

Our second guinea pig is List[Int], which is a container of (0 or more) Int.

val intList: List[Int] = List(1, 2, 3)
val mappedResult2: List[Float] = intList.map(halve)

We can see that an List[Int] turns into a List[Float], the inner values of the container are modified from Int to Float when mapped over with a function from Int to Float...

Our third is a hand made UselessContainer[Int], which is a container of exactly 1 Int.

final case class UselessContainer[A](innerValue: A)
val intContainer: UselessContainer[Int] = UselessContainer(99)
val mappedResult3: UselessContainer[Float] = intContainer.map(halve)

We can see that an UselessContainer[Int] turns into an UselessContainer[Float], the inner value of the container being modified from Int to Float when mapped over with a function from Int to Float... (I've deliberately hidden an implementation detail here for clarity, I'll cover it later)

So we can observe that pattern we described earlier:

A functor, let's call it F[A], is a structure containing a value of type A and which can be mapped over by a function of type A => B, getting back a functor F[B] containing a value of type B.

How do we abstract and encode that ability ?

Functors are usually represented by a type class.

As a reminder, a type class is a group of types that all provide the same abilities (interface), which make them part of the same class (group, "club") of same abilities providing types (see my article about type classes here.

This is the functor type class implementation:

trait Functor[F[_]]{
    def map[A, B](fa: F[A], func: A => B): F[B]
}

The types our functor type class abstract over are type constructors (F[_], our container types)
The type class exposes a map function taking a container F[A] of values of type A, a function of type A => B and return a F[B], a container of values of type B: the pattern we just described.

A note about type constructors: A type constructor is a type to which you have to supply an other type to get back a new type. You can think of it just as functions that take values to produce values. And that makes sense, since we have to supply to our container type the type of values it will "hold" !

Most used concrete type constructors are List[_], Option[_], Either[_,_], Map[_, _] and so on.

To illustrate what it means in your Scala code let's make our UselessContainer a functor:

implicit val ucFunctor = new Functor[UselessContainer] {
    override def map[A, B](fa: UselessContainer[A],
                           func: A => B): UselessContainer[B] =
      UselessContainer(func(fa.innerValue))
}

Be careful, if you attempt to create your own functor, it is not enough. You have to prove that your functor instance respects the functor's laws we stated earlier (usually via property based tests), hence that:

For all values uc of type UselessContainer:

ucFunctor.map(uc, identity) == uc

For all values uc of type UselessContainer and for any two functions f of type A => B and g of type B => C:

ucFunctor.map(uc, g compose f) == ucFunctor.map(ucFunctor.map(uc, f), g)

However, you can safely use functor instances brought to you by Cats or Scalaz because their implementations lawfulness are tested for you.

(You can find the Cats functor laws here and their tests here. They are tested with discipline.)

Now that you know what a functor is and how it's implemented in Scala, let's talk a bit about category theory !

An insight about the theory behind functors

During this article, we only talked about the most widely known kind of functors, the co-variant endofunctors. Don't mind the complicated name, they are all you need to know to begin having fun in functional programming.

However if you'd like to have a grasp a little bit of theory behind functors, keep on reading.

Functors are structure-preserving mappings between categories.

Tiny crash course into category theory

Category theory is the mathematical field that study how things relate to each others in general and how their relations compose.

A category is composed of:

Objects (view it as something purely abstract, absolutely anything, points for example)
Arrows or morphisms (which are the ways to go from one object to another)
And two fundamental properties:
- Composition: A way to compose these arrows associatively. It means that if it exists an arrow from an object a to an object b and an arrow from the object b to an object c, it exists an arrow that goes from a to c and the order of composition does not matter (given 3 morphisms that are composable f, g, h then (h . g) . f) == h . (g . f))
- Identity: There is an identity arrow for every object in the category which is the arrow which goes from that object to itself

A, B, C are this category's objects
f and g are its arrows or morphisms
g . f is f and g composition since f goes from A to B and g goes from B to C (and it MUST exist to satisfy composition law, since f and g exist)
1A, 1B and 1C are the identity arrows of A, B and C

Back to Scala

In the context of purely functional programming in Scala, we can consider that we work in a particular category that we are going to call it S (I won't go into theoretical compromises implied by that parallel, but there are some !):

S objects are Scala's types
S morphisms are Scala's functions
- Composition between morphisms is then function composition
- Identity morphisms for S objects is the identity function

Indeed, if we consider the object a (the type A) and the object b (the type B), Scala functions A => B are morphisms between a and b.

Given our morphism from a to b, if it exists an object c (the type C) and a morphism between b and c exists (a function B => C):

Then it must exist a morphism from a to c which is the composition of the two. And it does ! It is (pseudo code):
- For g: B => C and f: A => B, g compose f
And that composition is associative:
- (h compose g) compose f is the same as h compose (g compose f)

Moreover for every object (every type) it exists an identity morphism, the identity function, which is the type parametric function:

def id[A](a: A) = a

We can now grasp how category theory and purely functional programming can relate !

And then back to our functors

Now that you know what a category is, and that you know about the category S we work in when doing functional programming in Scala, re-think about it.

A functor F being a structure-preserving mapping between two categories means that it maps objects from category A to objects from category F(A) (the category which A is mapped to by the functor F) and morphisms from A to morphisms of F(A) while preserving their relations.

Since we always work with types and with functions between types in Scala, a functor in that context is a mapping from and to the same category, between S and S, and that particular kind of functor is called an endofunctor.

Let's explore how Option behaves (but we could have replaced Option by any functor F):

Objects

Objects in `S` (types)	Objects in `F(S)`
`A`	`Option[A]`
`Int`	`Option[Int]`
`String`	`Option[String]`

So Option type construtor maps objects (types) in S to other objects (types) in S.

Morphisms

Let's use our previously defined:

def map[A, B](fa: F[A], func: A => B): F[B].

If we partially apply map with a function f of type A => B like so (pseudo-code): map(_, f), then we are left with a new function of type F[A] => F[B].

Using map that way, let's see how morphisms behave:

Morphisms in `S` (function between types)	Morphisms in `F(S)`
`A => A` (identity)	`Option[A] => Option[A]`
`A => B`	`Option[A] => Option[B]`
`Int => Float`	`Option[Int] => Option[Float]`
`String => String`	`Option[String] => Option[String]`

So Option's map maps morphisms (functions from type to type) in S to other morphisms (functions from type to type) in S.

We won't go into details but we could have shown how Option functor respects morphism composition and identity laws.

What does it buy us ?

Functors are mappings between two categories
A functor, due to its theorical nature, preserves the morphisms and their relations between the two categories it maps
When programming in pure FP, we are in S, the category of Scala types, functions and under function composition. The functors we use are then endofunctors (from S to S) because they map Scala types and functions between them to other Scala types and functions between them

In programming terms, (endo)functors in Scala allow us to move from origin types (A, B, ...), to new target types (F[A], F[B], ...) while safely allowing us to re-use the origin functions and their compositions on the target types.

To continue with our Option example, Option type constructor "map" our types A and B into Option[A] and Option[B] types while allowing us to re-use functions of type A => B thanks to Options' map, turning them into Option[A] => Option[B] and preserving their compositions.

But that is not over ! Let's leave abstraction world we all love so much and head back to concrete world.

Concrete functors instances enhance our origin types with new capacities. Indeed, functor instances are concrete data structures with particularities (the one we said we did not care about at the beginning of that article), the abilty to represent empty value for Option, the ability to suspend an effectful computation for IO, the ability to hold multiple values for List and so on !

Ok, so, to sum up, why functors are awesome ? The two main reasons I can think of are:

Abstraction, abstraction, abstraction... Code using functors allows you to only care about the fact that what you manipulate is mappable.
- It increases code reuse since a piece of code using functors can be called with any concrete functor instance
- And it reduces a lot error risks since you have to deal with less particularities of the concrete, final, data structure your functions will be called with
They add functionnalities to existing types, while allowing to still use functions on them (you would not want to re-write them for every functor instances), and that's a big deal:
- Option allow you to bring null into a concrete value, making code a lot healthier (and functions purer)
- Either allow you to bring computation errors into concrete values, making dealing with computation errors a lot healthier (and functions purer)
- IO allow you to turn a computations into a values, allowing better compositionality and referential transparency
- And so on...

I hope I made a bit clearer what functors are in the context of category theory and how that translates to pure FP in Scala !

More material

If you want to keep diving deeper, some interesting stuff can be found on my FP resources list and in particular:

Scala with Cats - Functor chapter
Functors' section of the awesome Functors, Applicatives, And Monads In Pictures article
Yann Esposito's great "Category theory and programming"
Let me know if you need more

Conclusion

To sum up, we saw:

That a functor is a kind of container that can be mapped over by a function and the laws it has to respect
Some examples and identified a common pattern
How we abstract over and encode that pattern in Scala as a type class of type constructors
We had a modest overview about category theory, what functors are in category theory, and how both relates to pure FP in Scala
We concluded by how great functors are and for what practical reasons

I'll try to keep that blog post updated.
If there are any additions, imprecision or mistakes that I should correct or if you need more explanations, feel free to contact me on Twitter or by mail !

Edit: Thanks Jules Ivanic for the review :).