Associative binary operation for Option in Scala

Question

I remember that monad is a monoid. That is, there is an associative binary operation * so that if ma and mb are monadic values then ma * mb is a monadic value too.

If the above is correct, what is that binary operation for Option in Scala ? For example, what can be * in Some(1) * Some(2) ?

Answer 1

(This answer stole its definitions from https://stackoverflow.com/a/3870310/200266 and only tries to give a rough explanation. My knowledge of category theory is rather basic.)

In the generic case, saying that a monad is also a monoid is only valid, if you consider the functor (eg. T => Option[T]) and not the values (eg. Some(3) or None).

As an example for a monoid over values, let’s have a look at List[T].

We have a binary operation • : S × S -> S:

def append[T](list1: List[T], list2: List[T]): List[T] = list1 append list2

and the empty list Nil is obviously the identity element. There is no append method in every monad, though, so the above cannot be generalised onto all monads. Let’s change the definition of the binary operation a bit.

Now, in the above case × can be seen as returning a tuple of the input values:

List[T] × List[T] => (List[T], List[T])

And our append function receives this tuple as its input.

However, we may change the tupling operation × to ∘, now meaning functor composition.

(K => List[K]) ∘ (K => List[K]) => (K => List[List[K]])

And so, we’re looking for a function fulfilling μ : T ∘ T -> T or more specific

(K => List[List[K]]) => (K => List[K])

That operation is known in Scala as flatten (join in Haskell). The monoid’s identity element is the the monad constructor which has no generic name in Scala (return in Haskell), but which exists for every monad. Eg. x => List(x).

To wrap things up, considering this and the other answers in this question, there are three possibilities for how a monad can be a monoid:

A) Every monad is also a monoid in the above sense under functor composition.

B) Every monad M[T] has a monoid if there is also a monoid (with some binary operation ~+~) for T: for {x <- ma; y <- mb} yield x ~+~ y

C) Some monads may have one or more specific monoids which differs from the one in B. For example List’s append or Option’s orElse.

Answer 2

I think orElse is a valid associative binary operator:

def test(a: Option[Int], b: Option[Int], c: Option[Int]): Boolean =
  ((a orElse b) orElse c) == (a orElse (b orElse c))

Seq(Option(1), Option(2), None).permutations.forall {
  case Seq(a, b, c) => test(a, b, c)
}

This holds. I have used this property in a FingerTree implementation, it was proposed by Hinze & Paterson in their Haskell version, it is used to implement an interval tree.

Answer 3

An Option by itself is not a monoid just like an Integer is not a monoid by itself. A monoid is a type AND the associative binary operation.

You can consider the Integer type AND addition a monoid. Integer and multiplication are a monoid too. Turning two Integers to String and concatenating them ("2" + "3" = "23") is a valid associative operation too that could create a monoid with Integers: in fact ("2" concat "3") concat "4" = "2" concat ("3" concat "4") = "234".

The thing is, it's up to you to define the associative operation that completes the definition of "monoid" for a type, so your question "what is THE associative operation...." is not well-formed.

As with Integers, Option[Int] and addition or multiplications can be monoids, but an Option[Int] per se is not.

Like @senia does in his answer you can say "I can define a monoid based on Option[T] if T is itself a Monoid". In that case, the associative operation can use the one that was defined for T and Some[a] append Some[b] can be Some[a append b].

Or, as @0__ did, you can find a particular operation (orElse) that, together with Option[Int] makes a monoid. That is correct too (but notice how the answer starts with "orElse is a valid associative binary operator").

Answer 4

Actually not. Monad for Option is not a Monoid for Option[T]. Monad is defined for M[_] and Monoid is defined for T.

You can create Monoid for Option[T] if you have Monoid for T like this:

def optionMonoid[T: Monoid]: Monoid[Option[T]] = new Monoid {
  def zero: Option[T] = None
  def append(f1: Option[T], f2: => Option[T]): Option[T] = (fi, f2) match {
    case (None, None) => None
    case (Some(a), Some(b)) => Some(a |+| b)
    case (r @ Some(_), None) => r
    case (None, r @ Some(_)) => r
  }
}

Answer 5

There are two different senses of monoid. A monad is a monoid object in the category theory sense (see the last example there); it isn't a monoid in the abstract algebra sense (which most other answers are talking about).