/**
* Scala developer @Ebiznext,
* SNUG co-organizer.
* Exalted about FP and maintaining
* A list of great ressources !
*/
val me = SoftwareDeveloper(
firstname = "Martin",
name = "Menestret",
email = "here",
twitter = "@mmenestret"
)
Blog posts
Anatomy of functional programming
Anatomy of an algebra
Anatomy of a type class
A minimal Haskell development environment for beginners with VS Code
by Myself
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.
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:
A simple algebra example would be:
a + (b + c) = (a + b) + c
and a × (b × c) = (a × b) × c
a + b = b + a
and a × b = b × a
a + 0 = a
and a * 1 = a
When modeling a business domain, in functional programming, we separate strongly data from behaviors (see the Data/behavior relationship section).
To do that:
Doesn’t that ring any bell ?
We manipulate algebras !
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:
Amount
, Price
, ID
, Item
, Sales
, etc. (our business types)combineAll
, generateReport
(operations on those types)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.
ADT stands for algebraïc data type. Well, we talked a bit about algebras but we didn’t talk about types yet.
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 combinationsOption[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
)Here is Wikipedia’s definition of an algebraïc 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:
Sales
, Boolean
, String
, Int
, …)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:
Or less often:
Either[A, B]
typeThat 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.
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
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)
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) !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:
Or less often
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 !
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
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, ())
(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) !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.
If you want to keep diving deeper, some interesting stuff can be found on my FP resources list and in particular:
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 Algebraïc Data Types :).
To sum up, we learnt:
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 !
tags: Scala - Functional programming