Algebraic Structures
Tags: functional, scala
Published: 2020-10-14 03:15:20

[glossary]: https://www.linkedin.com/pulse/glossary-functional-programming-john-de-goes/
[kodumaro]: https://kodumaro.cacilhas.info/2020/10/algebra.html
[haskell]: https://www.haskell.org/
[IO]: https://wiki.haskell.org/Introduction_to_IO
[lies]: https://dev.to/cacilhas/lies-they-ve-been-telling-you-about-functional-programming-lh6
[scala]: https://www.scala-lang.org/
[scala.collection.immutable.Seq]: https://www.scala-lang.org/api/current/scala/collection/immutable/Seq.html
[scala.util.Try]: https://www.scala-lang.org/api/current/scala/util/Try.html
[type-iso]: https://dev.to/cacilhas/type-isomorphism-3bp9

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][lies], there are two very important main ideas: [algebraic data types][type-iso] (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][scala] is [`scala.util.Try`][scala.util.Try]:

```scala
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][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`][scala.collection.immutable.Seq]:

```scala
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`:

```scala
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`][IO]. The `IO` monad describes how an I/O side-effect happens.

For example:

```haskell
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:

```scala
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:

```scala
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:

```scala
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:

```scala
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][glossary].

-----

Original post in [Kodumaro][kodumaro].