Hands on Monoids in Scala

When we refactor code how can we be confident that we don't break anything?

3 of the most important things that allow us to refactor fearlessly are:

Side effect free - or pure - expressions
Statically typed expressions
Tests

In this article we will solely focus on the aspect of side effects and strictly speaking on how to identify them. Being able to identify side effects in our programs clearly is the precondition for eliminating them.

Why avoid side effects?

Continue reading →

Have you ever wanted to try out PureScript but were lacking a good way to get started?

If you

Have some prior functional programming knowledge - maybe you know Haskell,Elm,F#,or Scala,etc.
Want to solve a small task with PureScript
And want to get started quickly

This post is for you!

In this post we will walk through setting up and implementing a small exemplary PureScript application from scratch.

Continue reading →

In this article I would like to present a minimal implementation of a music data type and everything that is needed to turn that into audible sound from an Elm application.

We will see how to transcribe an existing composition - an excerpt from Chick Corea's Children's Songs No. 6 - and listen to the result right here,embedded in this article.

From a music data type to performance

My colleague Jonas recently pointed out the presentation Making Algorithmic Music by Donya Quick to me. Donya Quick shows how she uses the Haskell library Euterpea to produce algorithmic music.

It got me really excited about the idea of porting this to Elm and to be able to use this in web applications.

In the following we will see the core data types and algorithms from Euterpea ported to Elm. To focus on the core concepts the implementation is stripped down to the minimum that is required to transcribe and perform an existing polyphonic piece of music (for a single instrument).

Continue reading →

This post is about how to implement well structured,and purely functional command line applications in Scala using PureApp.

PureApp originated in an experiment while refactoring out some glue code of an interactive command line application. At the same time it was inspired by the Elm Architecture Pattern,and scalaz's SafeApp,as well as scalm.

To show the really cool things we can do with PureApp,we will implement a self-contained example application from scratch.

This application translates texts from and into different languages. And it provides basic user interactions via the command line.

The complete source code is compiled with tut. Every output (displayed as code comments) is generated by tut.
Continue reading →

In this post we will see how applicatives can be used for validation in Scala. It is an elegant approach. Especially when compared to an object-oriented way.

Usually when we have operations that can fail,we have them return types like Option or Try. We sequence operations and once there is an error the computation is short circuited and the result is a None or a Failure.

Applicatives allow us to compose independent operations and evaluate each one. Even if an intermediate evaluation fails. This allows us to collect error messages instead of returning only the first error that occurred.

A classic example where this is useful is the validation of user input. We would like to return a list of all invalid inputs rather than aborting the evaluation after the first error.

Scala Cats provides a type that does exactly that. So let's dive into some code and see how it works.

Continue reading →

After some initial struggles,the chapter Functional Parsers from the great book Programming in Haskell by Graham Hutton,where a basic parser library is built from scratch,significantly helped me to finally understand the core ideas of parser combinators and how to apply them to other programming languages other than Haskell as well.

While I recently revisited the material and started to port the examples to Scala I wasn't able to define a proper monad instance for the type Parser[A].

The type Parser[A] alias was defined like this:

type Parser[A] = String =>Option[(A,String)] // defined type alias Parser

To test the monad laws with discipline I had to provide an instance of Eq[Parser[A]]. Because Parser[A] is a function,equality could only be approximated by showing degrees of function equivalence,which is not a trivial task.

Also the implementation of tailRecM was challenging. (I couldn't figure it out.)

Using existing abstractions

Continue reading →

Most config libraries use a stringly typed approach.

Some handle runtime failures due to invalid configuration schemas by leveraging data types like Option or Result to represent missing values or errors. This allows us to handle these failures by either providing default values or by providing decent error messages.

This is a good strategy that we should definitely stick to.

However,the problem with default values is that we might not even notice if the configuration is broken. This could potentially fail in production. In any case an error e.g. due to a misspelled config property will be observable at runtime at the earliest.

Wouldn't it be a great user experience (for us developers) if the compiler told us if the configuration schema is invalid? Even better,imagine we could access the configuration data in a strongly typed way like any other data structure,and with autocompletion.

Moreover,what if we didn't have to write any glue code,not even when the configuration schema changes?

This can be done with the costs of an initial setup that won't take more than probably around 5 minutes.

Continue reading →

In this post I will look at a practical example where the combined application (through monad transformers) of the state monad and the either monad can be very useful.

I won't go into much theory,but instead demonstrate the problem and then slowly build it up to resolve it.

You don't have to be completely familiar with all the concepts as the examples will be easy to follow. Here is a very brief overview:

Continue reading →

If your API overflows with Boolean parameters,this is usually a bad smell.

Consider the following function call for example:

toContactInfoList(csv,true,true)

When looking at this snippet of code it is not very clear what kind of effect the two Boolean parameters will have exactly. In fact,we would probably be without a clue.

We have to inspect the documentation or at least the parameter names of the function declaration to get a better idea. But still,this doesn't solve all of our problems.

The more Boolean parameters there are,the easier it will be for the caller to mix them up. We have to be very careful.

Moreover,functions with Boolean parameters must have conditional logic like if or case statements inside. With a growing number of conditional statements,the number of possible execution paths will grow exponentially. It will become more difficult to reason about the implementation code.

Can we do better?

Sure we can. Lambdas and combinators come to the rescue and I'm going to show this with a simple example,a refactoring of the function from above.

This post is based on a great article by John A De Goes,Destroy All Ifs — A Perspective from Functional Programming.

I'm going to take John's ideas that he backed up with PureScript examples and present how the same thing can be elegantly achieved in Scala.

Continue reading →

I'm currently working on an sbt plugin that generates Scala case classes at compile time to model JSON API responses for easy deserialization especially with the Scala play-json library.

The plugin makes it possible to access JSON documents in a statically typed way including auto-completion. It takes a sample JSON document as input (either from a file or a URL) and generates Scala types that can be used to read data with the same structure.

Let's look at a basic example,an app that prints the current Bitcoin price to the console.

Continue reading →

What do Monoids in Scala have to do with birdwatching?

Before I come to that I would like to mention that since I'm coming from F# and recently started with Scala, being able to use type classes in my code is new to me.

I find this really exciting which I'd like to share.

So this post is maybe not a complete cohesive tutorial an Monoids but I hope that it is a fun little teaser for looking into things like functional programming, Scala, Cats, Haskell, type classes or maybe even category theory.

Let's start

Imagine we have to aggregate many lists of bird counts.

A single list of bird counts is represented by a map of type Map[(Date, Location, Species), Int].

The objective is to create a function that takes many of these maps and combines them into a single map of aggregated counts. For equal keys the counts should be summed up.

This is the signature of the function:

def aggregate(birdCounts: List[Map[(Date, Location, Species), Int]]) = ???

Here is an example input:

List(
  Map(
    (Date(2016, 1, 4), cologne, pigeon) -> 37,
    (Date(2016, 1, 11), bonn, starling) -> 64,
    (Date(2016, 1, 18), cologne, bullfinch) -> 54
  ),
  Map(
    (Date(2016, 1, 18), cologne, bullfinch) -> 60,
    (Date(2016, 1, 18), bonn, bullfinch) -> 2,
    (Date(2016, 1, 25), dusseldorf, bullfinch) -> 75
  ),
  Map(
    (Date(2016, 1, 4), cologne, pigeon) -> 30
  )
)

Expected output:

Map(
  (Date(2016, 1, 4), cologne, pigeon) -> 67,
  (Date(2016, 1, 11), bonn, starling) -> 64,
  (Date(2016, 1, 18), cologne, bullfinch) -> 114,
  (Date(2016, 1, 18), bonn, bullfinch) -> 2,
  (Date(2016, 1, 25), dusseldorf, bullfinch) -> 75
)

This looks like a nice little programming kata.

The direct approach

There are different approaches on how to solve this.

I don't even want to think about the imperative way.

So let's look at a declarative (or functional) way of solving this:

birdCounts
  .flatMap(_.toList)
  .groupBy(_._1)
  .map({ case (k,v) => (k, v.map(_._2).sum) })

A more general abstraction

The functional solution seems to work.

But there is a more general abstraction to this that we can take advantage of.

I will give it away, right away, this is the solution:

import cats.implicits._

birdCounts.combineAll

That's it!

I think, this is pretty cool.

But why does this work?

It works because in this context:

The type Map[A, B] is a Monoid
The type Int is a Monoid
And there is a default implementation in the library Cats for these types and type classes

Cats and type classes

Cats is a library which provides abstractions for functional programming in Scala and a very big part of these abstractions are type classes.

Type classes originated in Haskell. A type class defines a set of operations that must be supported by all instances of that type class.

There are lots of existing and commonly used type classes but we can also define our own.

Instances of a type class are normal types that we usually work with like String, Int, List, ... or any other type, whether built-in, custom or coming from some external library.

The cool thing is that these existing types can be extended with the type class functionalities without changing the original code. There is no need for inheritance, or subtyping.

How does this work and what is a Monoid?

A Monoid is such a type class and relates to category theory. (Also see Categories Great and Small).

Here comes a quick summary of what a Monoid is.

Recap on Monoids

A Monoid consists of a type together with:

A binary operation for combining values (sometimes called combine or append)
A value that doesn't do anything when combined with others (sometimes called empty, identity or neutral element)

In addition to that the Monoid must satisfy the Monoid laws, associativity and left and right identity. (Which will not be further discussed here. If you are interested please refer to Monoid laws.)

Examples

A simple example of a Monoid is the type Int together with + as the binary operation and 0 as the neutral element.

Other examples are:

Type Int with operation * and neutral element 1
Type String with operation String.concat and neutral element String.empty
Type List with operation ++ and neutral element List.empty
Type Boolean with the operation && and the neutral element true
Type A => A with the operation andThen (function composition) and the neutral element (x: A) => x (identity function)
...

Let's explore that a bit.

Prerequisites to following along the next steps are that Scala and sbt are installed. Also Scala and sbt should be added to the system's path variable.

Follow these steps to start the Scala REPL with the Cats library loaded:

Create a new directory
Create an empty file build.sbt inside this directory
Put this line inside build.sbt: libraryDependencies += "org.typelevel" %% "cats" % "0.8.0"
Open a terminal and navigate to the directory
Start sbt by typing sbt
Start the Scala REPL by typing console

First let's import the needed dependencies:

scala> import cats.Monoid
import cats.Monoid

scala> import cats.implicits._
import cats.implicits._

Now we can try out some things.

Let's start with the first Monoid example from above (Int, +, 0).

scala> Monoid[Int].empty
res1: Int = 0

scala> Monoid[Int].combine(1,2)
res2: Int = 3

We can combine a list of integers with combinAll:

scala> (1 to 10).toList.combineAll // = 0+1+2+3+4+5+6+7+8+9+10
res4: Int = 55

Under the covers combineAll is doing a fold over the list where Monoid[Int] is 0 and combine is addition:

scala> (1 to 10).fold(Monoid[Int].empty)((a,b) => a.combine(b))
res0: Int = 55

... which is the same as:

scala> (1 to 10).fold(0)(_ + _)
res1: Int = 55

Here is a diagram which shows how a left fold for a list of type List[Monoid[Int]] works. First the neutral element and the first element of the list are applied to the addition function. Then this result and the second element are added and so on.

            ------------ Monoid[Int].combine -------------
            |    |    |    |    |    |    |    |    |    |
            v    v    v    v    v    v    v    v    v    v
((((((((((0 + 1) + 2) + 3) + 4) + 5) + 6) + 7) + 8) + 9) + 10)
          ^
          |_ Monoid[Int].empty

With a Map type (as in the birdwatching problem) it works very similar:

scala> Monoid[Map[Long, Int]].empty
res5: Map[Long,Int] = Map()

scala> Monoid[Map[Long, Int]].combine(Map(1L -> 10), Map(1L -> 100, 2L -> 999))
res6: Map[Long,Int] = Map(1 -> 110, 2 -> 999)

It is important that the values of the map are of type Int. And that Int has a default Monoid implementation in Cats. Therefore the values for identical keys will be added together. This is exactly what we wanted in the opening example.

Creating our own instance of a Monoid

So far we have seen default implementations of Monoids that were provided by Cats.

Finally let's take a somewhat more advanced example and see how an instance of a Monoid can be created in Scala.

Let's define a class Point:

case class Point(x: Int, y: Int)

Imagine we have a function that represents a move from one point to another. It takes a starting point as an input parameter and returns the destination point. It has this signature:

Point => Point

We can define some values of that type:

scala> val up = (p: Point) => Point(p.x, p.y + 1)
up: Point => Point = <function1>

scala> val down = (p: Point) => Point(p.x, p.y - 1)
down: Point => Point = <function1>

scala> val right = (p: Point) => Point(p.x + 1, p.y)
right: Point => Point = <function1>

scala> val left = (p: Point) => Point(p.x - 1, p.y)
left: Point => Point = <function1>

scala> val stay = (p: Point) => p.copy()
none: Point => Point = <function1>

Now we can define the type Point => Point as an instance of Monoid[Point => Point] where the neutral element is stay and the combine operation is function composition andThen:

implicit val moveMonoid: Monoid[Point => Point] = 
  new Monoid[Point => Point] {
    def empty = stay

    def combine(m1: Point => Point, m2: Point => Point) = 
      m1 andThen m2
  }

(The code above can be executed in the REPL by using the paste mode. Type :paste. Then the code can be pasted. Press ctrl-D to quit paste mode.)

Using the new Monoid:

scala> val move = List(up, up, up, right, right, down, left, stay).combineAll
move: Point => Point = <function1>

scala> move(Point(0,0))
res6: Point = Point(1,2)

Conclusion

We have seen how Monoids can help with combining maps, a trivial but very common use case.

The concept of Monoids is very simple and powerful and it is very useful in many other situations.

They can be the building blocks of other more complex types such as the Writer Monad e.g.

Also Monoids are extensively used in data processing libraries like e.g. Twitter's Algebird.

If this got you interested, follow along the hands-on, play around with it, use Cats in your next project or find out more about functional programming or category theory.

Have fun!

Leif Battermann

Functional Programming Fu

Identify Side Effects And Refactor Fearlessly

Why avoid side effects?

PureScript Case Study And Guide For Newcomers

Elm And The Algorithm Of Music

From a music data type to performance

Interactive Command Line Applications In Scala –Well Structured And Purely Functional

How To Use Applicatives For Validation In Scala And Save Much Work

Parsers in Scala built upon existing abstractions

Using existing abstractions

Strongly Typed Configuration Access With Code Generation

Error and state handling with monad transformers in Scala

Use lambdas and combinators to improve your API

Modelling API Responses With sbt-json –Print Current Bitcoin Price

Leif Battermann

Functional Programming Fu

Hands on Monoids in Scala – Applying categories to birdwatching

Let's start

The direct approach

A more general abstraction

But why does this work?

Cats and type classes

How does this work and what is a Monoid?

Recap on Monoids

Examples