Nio Nio - 1 month ago 18
Scala Question

Correct use of term Monoid

From the following example, I think it is correct to say that

String
defines a monoid under the concatenation operation since it is an associative binary operation and
String
happens to have an identity element which is an empty string
""
.

scala> ("" + "Jane") + "Doe" == "" + ("Jane" + "Doe")
res0: Boolean = true


From the various texts I have been reading on the subject lately, it seems that the correct use of the term monoid is that the monoid is actually a combination of both the type (in this case
String
) and an instance of some monoid type which defines the operation and identity element.

For example, here is a theoretical
Monoid
type and a concrete instance of it as seems to be commonly defined in various books/articles:-

trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}

val stringMonoid = new Monoid[String] {
def op(a1: String, a2: String) = a1 + a2
val zero = ""
}


I know that we do not need
trait Monoid[A]
nor
stringMonoid
to be defined in the core (Scala, or rather Java) library to support my REPL output and that the example is just a tool to understand the abstract concept of a monoid.

My issue (and I am very possibly thinking about it way too much) is the purist definition. I know that the underlying
java.lang.String
(or rather
StringBuilder
) already defines the associative operation, but I do not think that there is an explicit definition of the identity element (in this case just an empty string
""
) defined anywhere.

Question:-

Is
String
a monoid under the concatenation operation implicitly, just because we happen to know that using an empty string
""
provides the identity? Or is it that an explicit definition of the identity element for a type is unnecessary for it to be classed as a monoid (under a particular associative binary operation).

Answer

I think that you already understand the concept right and indeed "think too much" about it (;

A monoid is a triple as they say in mathematics: a set (think of a type with its values), an associative binary operator on it and a neutral element. You define such triple — you define a monoid. So the answer to

Is String a monoid under the concatenation operation implicitly, just because we happen to know that using an empty string "" provides the identity?

is simply yes. You named the set, the associative binary operation and the neutral element — bingo! You got a monoid! About

already defines the associative operation, but I do not think that there is an explicit definition of the identity element

there's a bit of confusion. You can choose different associative operations on String with their corresponding neutral elements and define various monoids. Concatenation is not like some kind of "orthodox" associative operation on String to define monoid, just, probably, the most obvious.

If you define a table as something "with four legs and a flat horizontal surface on them", then anything that fits this definition is a table, regardless of the material it's made and other variable characteristics. Now, when do you need to "certify" it explicitly is a table? Only when you need to use its "table-properties", say if to sell it and advertise that you can put things on it and they won't fall off, because the surface is guaranteed to be flat and horizontal.

Sorry, if the example is kind of stupid, I'm not very good in such analogies. I hope it is still helpful.


Now about instantiating the mentioned "theoretical Monoid type". Such types are usually called a type class. Neither existence of such type itself (which can be defined in various ways), nor its instance are necessary to call the triple (String, (_ ++ _), "") a monoid and reason about it as a monoid (i.e. use general monoid properties). What it is actually used for is ad-hoc polymorphism. In Scala it is done with implicits. One can, for example, define a polymorphic function

def fold[M](seq: Seq[M])(implicit m: Monoid[M]): M = seq match {
  case Seq.empty => m.zero
  case (h +: t)  => m.op(h, fold(t))
}

Then if your stringMonoid value is declared as implicit val, whenever you use fold[String] and stringMonoid is in scope, it will use its zero and op inside. Same fold definition will work for other instances of Monoid[...].

Another topic is what happens when you have several instances of Monoid[String]. Read Where does Scala look for implicits?.