Algebraic Structures

For a developer to be able to work with Functional Programming, there are a few concepts they must master.

In addition to the functional constraints, there are two very important main ideas: algebraic data types (ADT) and algebraic structures. In this post, we’re looking at some algebraic structures.

Functor

Functor is the simplest algebraic structure. It’s a wrapper around data that can map operations over them and their successful results.

A basic functor example in Scala is scala.util.Try:

Try(1 / x)
  .map(e => e*e)
  .map(1 - _)
  .map(_.toString) match {
    case Success(value) => s"the result is $value"
    case Failure(exc)   => s"it raised an exception: $exc"
  }

Most of the Scala basic wrappers, like Seq/List, Option, Either, etc, are functors too.

Monad

Haskell’s monads have been getting people in dread, but they’re nothing than a variation of functor approach.

A monad is a wrapper around data that can operate over them flatly mapping the results and possibly describing side-effects.

Our first monad example is the Seq:

Seq(1, 2, 3)
  .flapMap(e => Seq(e * 2))
  .flatMap(e => if (e == 2) Nil else Seq(e))
  .flatMap(e => if (e == 3) Seq(4, 5) else Seq(e))

The result is Seq(4, 5, 6); the flatMap method is the main resource of a monad.

Since Seq is a functor too, you may replace the first flatMap by a map, and it has a filter method, more expressive than flatMap:

Seq(1, 2, 3)
  .map(_ * 2)
  .filter(_ != 2)
  .flatMap(e => if (e == 4) Seq(4, 5) else Seq(e))

The result is the same. List, Option, Try, Either, etc, are monads too.

The knownest monad is the Haskell’s IO. The IO monad describes how an I/O side-effect happens.

For example:

greetings :: IO ()
greetings = printStrLn "Hello, World!"

The greetings function idempotently returns an IO monad that can trigger a writing to the standard output.

Monoid

A monoid is a structure that supplies an operation and a unit instance for that operation and type.

The monoid definition is:

trait Monoid[A] {
  def op(a: A, b: A): A
  def unit[A]: A
}

Let’s, for instance, define two monoids for dealing with integer and string sequences:

given object IntMonoid extends Monoid[Int] {
  def op(a: Int, b: Int): Int = a + b
  def unit: Int = 0
}

given object StringMonoid extends Monoid[String] {
  def op(a: String, b: String): String = a concat b
  def unit: String = ""
}

Defined these two monoids, we can code a function that can reduce an integer or string sequence:

def reduce[A](xs: Seq[A])(using ev: Monoid[A]): A =
  if (xs.isEmpty) ev.unit
  else ev.op(xs.head, reduce(xs.tail))

It works like this:

reduce(Seq(1, 2, 3)) // returns 6
reduce(Seq("Hello", ", ", "World", "!")) // returns "Hello, World!"

In order for the reduce function to work properly with other types, it’s enough to supply another type’s implicit monoid, for instance a DoubleMonoid, no need for changing the reduce function.

Apply, applicative, semiring, lattice, etc

Other algebraic structures are mostly just variants of these three we’ve just been through. You can find some definitions in this glossary.

---

Original post in Kodumaro.

Comments

[Montegasppα Cacilhας]

I forgot to mention, an example of Scala’s built-in monoid is Numeric: the addition method is ev.plus, and the unit is ev.zero.