Algebraic Structures

2020-10-14
The shadows behind the code.

Scala

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

A simple 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 IntSumMonoid extends Monoid[Int] {
  def op(a: Int, b: Int): Int = a + b
  def unit: Int = 0
}

given object StringConcatMonoid 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.

[update]

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

[/update]

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.


Also in DEV.to.