3장 모노이드(Monoid)

3.1 Monoid란 무엇인가?

모노이드(Monoid)에 대해 이야기하기 전에, 집합(Set)과 마그마(Magma), 반군(Semigroup)에 대해 먼저 이야기하고 넘어가겠다.

Set과 Magma, Semigroup, 그리고 Monoid는 모두 추상대수학에서 나온 개념이다. 그렇다고 너무 어렵게 생각할 필요는 없다. 우리가 그런 용어를 모르고 있을 뿐이지, 각각의 용어가 설명하는 개념에 대해서는 익숙히 알고 있는 내용이기 때문이다.

먼저 Set은 우리가 흔히 말하는 집합을 말한다. 여기에 이항 연산자가 추가되면 Magma가 된다. 예를 들어, '정수'는 집합이다. 여기에 '덧셈'이라는 이항 연산을 묶은 것을 Magma라고 한다. Magma가 결합 법칙을 만족하면 Semigroup이 된다. 결합 법칙은 연산의 결과가 연산의 순서에 영향을 받거나 받지 않는 것을 말한다. 정수의 덧셈을 보면, 5+2+4 의 연산에 대해 (5+2)+4 와 5+(2+4)의 결과는 항상 같다. 즉, 정수의 덧셈은 결합 법칙을 만족한다. 반면에 정수의 뺄셈은 결합 법칙을 만족하지 않는다. (5-2)-4는 5-(2-4)의 결과는 같지 않다.

그렇다면, 모노이드는 무엇일까? Wikipedia에서는 모노이드에 대해 다음과 같이 설명하고 있다.

추상대수학에서 모노이드는 항등원을 갖는, 결합 법칙을 따르는 이항 연산을 갖춘 대수 구조이다. - wikipedia

Set, Magma, Semigroup과 연관시켜보면, Semigroup이 항등원을 가질 때 그걸 모노이드라고 할 수 있다. 정확히는, 결합 법칙과 항등 법칙을 합쳐서 모노이드 법칙이라고 부르며 모노이드 법칙을 만족하는 대수적 구조를 모노이드라고 한다.

모노이드를 Scala trait으로 표현하면 다음과 같다. (개념 설명을 위한 예시로서 실제로 scalaz 등에서 구현된 내용과는 다를 수 있다.)

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

trait Monoid의 구현은 op와 zero에 대해 다음의 성질을 만족해야 한다.

op(op(x, y), z)는 op(x, op(y, z))와 동등하다. op(x, zero)는 x와 동등하며, op(zero, x) 역시 x와 동등하다. 결합 법칙과 항등 법칙을 만족하는 예로 무엇이 있을까? 우리는 정수의 덧셈이 결합 법칙을 만족한다는 것과, 덧셈의 항등원이 0이라는 것을 알고 있다. 정수의 곱셉은 어떤가. 정수의 곱셈 역시 결합 법칙을 만족하며 그 항등원은 1이 된다. 다시 말해, 정수의 덧셈과 정수의 곱셈 연산은 각각 하나의 모노이드라고 할 수 있다. 이를 코드로 표현해보면 다음과 같다.

정수의 덧셈

val intAdditionMonoid = new Monoid[Int] {
  def op(a1: Int, a2: Int): Int = a1 + a2
  def zero = 0
}

정수의 곱셈

val intMultiplicationMonoid = new Monoid[Int] {
  def op(a1: Int, a2: Int): Int = a1 * a2
  def zero = 1
}

이 외에도, 문자열이나 목록의 결합 연산 역시 모노이드로 표현할 수 있다.

String Concatenation

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

List Concatenation

val listConcatMonoid[A] = new Monoid[List[A]] {
  def op(a1: List[A], a2: List[A]): List[A] = a1 ++ a2
  def zero = Nil // scala에서 Nil은 empty list와 같다
}

Option

val optionMonoid[A] = new Monoid[Option[A]] {
  def op(a1: Option[A], a2: Option[A]): Option[A] = a1 orElse a2
  val zero = None
}

3.2 Monoid의 이점

모노이드가 무엇인지는 알겠다. 그런데 왜 모노이드에 대해 알아야 하는 걸까? 모노이드는 Foldable을 지원하는 자료 구조에 대해 접기 연산을 할 수 있다는 것과, 그러한 연산을 병렬로 처리할 수 있다는 말과 같기 때문이다.

Foldable은 목록을 하나로 축약하는 것을 말한다. 정수 목록 List(1, 2, 3, 4)를 생각해보자. 4개의 항목이 있는 이 목록을 하나로 축약하려면 각각의 항목이 하나로 합쳐질 때의 연산이 필요하다. 각각의 항목을 모두 더하면서 하나로 만든다고 가정해보면, 결국 List(1, 2, 3, 4)를 접는 것은 1과 2를 더하고, 그 결과에 3을 더하고, 다시 그 결과에 4를 더한다는 것이다. 즉, ((1+2)+3)+4이다.

앞에서 정수의 덧셈이 모노이드이며 intAdditionMonoid로 표현할 수 있다는 것을 알고 있다. 정수 x와 정수 y의 덧셈 연산은 op(x, y)로 표현할 수 있는 것이다. 따라서 List(1, 2, 3, 4)에 대한 접기 연산은 접는 방향에 따라 다음과 같이 표현할 수 있다.

op(op(op(1, 2), 3), 4) // foldLeft
op(1, op(2, op(3, 4))) // foldRight

모노이드는 결합 법칙을 만족하기 때문에 intAdditionMonoid에서 위의 두 연산은 동일한 결과를 반환한다. 접는 과정에서의 연산을 덧셈이 아니라 뺄셈으로 변경한다면 접는 방향에 따라 foldLeft와 foldRight의 결과가 달라질 것이다. 그렇다면 모노이드에 대해 다음과 같은 연산은 어떨까?

op(op(1, 2), op(3, 4))

이 역시 결과는 같다. 하지만 앞서의 두 연산과 비교해보면 작지만 큰 차이가 있다. 1부터 4까지의 덧셈 연산을 위와 같이 표현할 수 있다는 것은, op(1, 2) 연산과 op(3, 4) 연산을 병렬로 수행할 수 있다는 의미이다.

op(op(op(1, 2), 3), 4)의 경우 op(1, 2)가 먼저 수행되어야만 그 결과인 3을 가지고 op(3, 3) 연산을 수행할 수 있다. 그에 비해 op(op(1, 2), op(3, 4))의 표현은 op(1, 2)와 op(3, 4)의 연산이 동시에 수행되어도 무방하리라는 것을 짐작할 수 있다.

즉, 모노이드는 결합 법칙을 만족하기 때문에 연산을 병렬적으로 수행할 수 있는 유연성을 가지게 된다.

3.3 정리

이번 장에서 처음으로 대수적 특징을 활용하는 사례를 살펴보았다. 모노이드 특질은 명칭이 갖는 의미보다 더 중요한 것이 있다. 바로 모노이드를 만족하면 자유롭게 동시성 프로그래밍의 여러 문제에서 해방 된다는 것이다. 멋진 일이지 않은가? 아무런 신경을 쓰지 않고도 멀티 스레드 프로그래밍을 할 수 있다니. 이제 더 멋진 녀석들을 만나러 가자.

Ch3. 모노이드