Applicative Programming 10

Monoid. Definition

A monoid is a data structure (you may think of it as a set, but sets have nothing to do with algebra) with an associative binary operation + and a neutral element for this operation.

A neutral element is defined as such element 0 that 0+a == a and a+0 == a for each a.

A neutral element is unique: if we had two, 0 and 0', then 0 + 0' == ... you got it.

Note, while the operation here is denoted as +, it does not mean it is commutative like a regular number addition. You know that not all + operation are commutative: take string concatenation.

Semigroup. Definition

If we did not have the neutral element, but just an associative binary operation, this would be called a semigroup. A monoid ia semigroup with a neutral element. Below I define a monoid, and a value holder class. For some reasons that I'll explain later this holder class is parameterized; but it does not actually depend on its parameter.

    trait Semigroup[T] {
      def add(x: T, y: T): T

      // А is a so-called phantom parameter; it is not being used, but works as a marker.
      // You can safely ignore it. Except that our code won't compile without it.
      case class Value[A](value: T) {
        def +(another: T): T = add(value, another)
      }

      implicit def value[A](x: T): Value[A] = Value(x)
    }

We have defined a semigroup here; the value holder class has addition defined. Further down we will see examples.

trait `Monoid`

Now to monoid. Add a neutral element _0, and let's throw in applicativity while we are at it. The applicativity here is simple: it is a constant functor mapping each type into Value type. Applicativity is build from monoid operations.

    trait Monoid[X] extends Semigroup[X] { // X is the type of values, e.g. Int, or String
      val _0: X // neutral element

      // constant functor into Values
      object App extends ConstantFunctor[Value] with Applicative[Value] {

        // pure zero
        override def pure[A](a: A) = value[A](_0)

        // have two constant functors; fold consists of adding their values
        override implicit def applicable[A, B](ff: Value[A => B]) = new Applicable[A, B, Value] {
          def <*>(fa: Value[A]) = Value(ff + fa.value)
        }
      }

      // this is the most generic map/reduce: traverse a traversable, sum up the values
      def accumulate[A,T[_]](traversable: Traversable[T])(eval: A => X)(ta: T[A]): X = {
        val evalAndWrap: A => Value[X] = eval andThen value
        traversable.traverse(App)(evalAndWrap)(ta).value
      }
    }

One can ask how come we add an ff and a fa.value? See, we deal with constant functors; so the value of one is added to the value of another. ff, being of type Value, has the method +.

We did cover Traversable in part 8.

Monoid. Examples

    object IntMonoid extends Monoid[Int] {
      val _0 = 0
      def add(x: Int, y: Int) = x + y
    }
  
    object StringMonoid extends Monoid[String] {
      val _0 = ""
      def add(x: String, y: String) = x + y
    }

    trait ListMonoid[T] extends Monoid[List[T]] {
      val _0 = Nil
      def add(x: List[T], y: List[T]) = x ++ y
    }

Traverse a Tree

Note that, once we define a monoid, we can traverse lists, trees, finger trees, anything that can be traversed, and sum up the values.

Remember the tree from part 8? Let's traverse it with a monoid.

    import StringMonoid._
    import TraversableTree._
    def tree(s: String) = Node(Leaf("" + s(0)), Node(Leaf("" + s(1)), Leaf("" + s(2))))
    val sut: Tree[String] = tree("abc")
    val collected: String = traverse(StringMonoid.App)((s: String) => "<<" + s + ">>")(sut).value
    collected must_== "<<a>><<b>><<c>>"

Accumulating Errors

Let's assume we have some kind of calculations that return an Either; the left part is for some kind of errors that we'd rather not drop, but accumulate in a semigroup (can be just a list of exceptions, or a list of error messages); we can turn it into an applicative functor, like in the following code:

    trait AccumulatingErrors[Bad] {
      val errorLog: Semigroup[Bad]
      implicit def acc(err: Bad) = errorLog.value(err)
      type Maybe[T] = Either[Bad, T]

      object App extends Applicative[({type Maybe[A] = Either[Bad, A]})#Maybe] with RightEitherFunctor[Bad] {

        def pure[A](a: A):Either[Bad, A] = Right[Bad, A](a)

        implicit def applicable[A, B](maybeF: Either[Bad, A => B]) = {
          new Applicable[A, B, Maybe] {

            def <*>(maybeA: Maybe[A]) = (maybeF, maybeA) match {
              case (Left(badF), Left(badA)) => Left(badF + badA)
              case (Left(badF), _)          => maybeF
              case (Right(f),  Left(badA))  => maybeA
              case (Right(f), Right(a))     => Right(f(a))
            }
          }
        }
      }
    }

We can make things more complicated and instead of a list of errors have a tree of errors:

    trait Oops
    case class Omg(what: String) extends Oops
    case class OiVei(first: Oops, second: Oops) extends Oops

    object Accumulator extends AccumulatingErrors[Oops] {
      val errorLog =  new Semigroup[Oops] { def add(x: Oops, y: Oops) = OiVei(x, y) }
    }
    implicit def applicable[A, B](maybeF: Either[Oops, A => B]) = Accumulator.App.applicable(maybeF)

Now define a good and a bad function, and a good and a bad string. Good ones return "right" values; bad ones return "left" values, with an error within.

    val goodFun    = Right((s: String) => "<<" + s + ">>")
    val badFun     = Left(Omg("snafu"))
    val goodString = Right("I am good")
    val badString  = Left(Omg("I'm bad"))

See what we get if we apply them to each other:

    goodFun <*> goodString must_== Right("<<I am good>>")
    goodFun <*> badString  must_== Left(Omg("I'm bad"))
    badFun  <*> goodString must_== Left(Omg("snafu"))
    badFun  <*> badString  must_== Left(OiVei(Omg("snafu"), Omg("I'm bad")))

This is the end of the series.

For further reading, just look up "applicative functor"

Provide feedback

Saved searches

Use saved searches to filter your results more quickly