Geekcephale

/**
  * 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

» Talks

» FP learning resources

6 October 2018

Anatomy of an algebra

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.

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:

A simple algebra example would be:

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:

Doesn’t that ring any bell ?

We manipulate algebras !

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:

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).

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:

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:

Or less often:

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):

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:

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):

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):

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:

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:

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