프로필 사진
Sojin Park
Frontend Dev

모노이드
모노이드의 정의와 예시, 그리고 범주와의 연관성
2019. 2. 9.

모노이드Monoid는 추상대수학에서 다루는 구조 중 하나이다.

집합에서의 정의

집합 MM과 이항 연산 :M×MM\cdot : M \times M \rightarrow M가 있어서

  • (결합법칙) 모든 a,b,cMa, b, c \in M에 대해서 (ab)c=a(bc)(a \cdot b) \cdot c = a \cdot (b \cdot c)가 성립하고,
  • (항등원의 존재) 모든 aMa \in M에 대해 1a=a1=a1 \cdot a = a \cdot 1 = a가 성립하는 1M1 \in M이 존재할 때

(M,)(M, \cdot)을 모노이드(Monoid)라고 한다.

모노이드의 예시

0을 포함한 자연수 집합 N\mathbb N과 덧셈 연산 ++

모든 a,b,cNa, b, c \in \mathbb N에 대해서

(a+b)+c=a+(b+c) (a + b) + c = a + (b + c)

가 성립함은 잘 알려져 있는 성질이다. (때문에 덧셈에서 괄호를 생략하여 a+b+ca + b + c처럼 쓸 수 있다.) 즉, 0을 포함한 자연수 집합 N\mathbb N과 이항 연산 ++는 결합법칙을 만족시킨다.

또한 00

a+0=a a + 0 = a

그리고

0+a=a 0 + a = a

를 만족시키므로, 항등원 역시 00으로 존재한다. (여기에서 두 번째 식 0+a=a0 + a = a는 덧셈의 교환법칙을 만족하는 성질으로 인해 필요가 없지만 모노이드에서 교환법칙은 필요조건이 아님에 주의하자.)

따라서 0을 포함한 자연수 집합 N\mathbb N과 덧셈 연산 ++은 모노이드를 이룬다.

프로그래밍에서 문자열 연결 연산

전체 문자열의 집합 SS에 대해 문자열을 연결하는 이항 연산 ++

abc"+def"=abcdef" abc" +def" = ``abcdef"

로 나타낸다고 생각하자. 그러면 모든 문자열 a,b,cSa, b, c \in S에 대해서

(a+b)+c=a+(b+c) (a + b) + c = a + (b + c)

가 성립하므로, 문자열 연결 연산 ++은 문자열 집합 SS에 대해 결합법칙을 만족한다.

또한 모든 문자열 aSa \in S와 빈 문자열 "``"에 대해

a+"=a"+a=a \begin{aligned} a + " &= a \\" + a &= a \end{aligned}

가 성립하므로, "``"은 항등원이다. 따라서 문자열 전체 집합 SS와 연결 연산 ++은 모노이드를 이룬다.

여기에서 문자열 연결 연산 ++는 교환법칙이 성립하지 않음에 주의하자. 예를 들어,

abc"+def"=abcdef"def"+abc"=defabc" \begin{aligned} abc" +def" &= abcdef"\\def" + abc" &=defabc" \end{aligned}

이다. 모노이드에서는 교환법칙이 성립하는 것이 필수 조건이 아니다.

범주론에서 모노이드

범주론에서 모노이드는 대상이 하나만 존재하는 범주Category를 가리킨다. 이는 이름에 Mono가 포함된 것에서 확인할 수 있다.

모노이드를 범주로 보기 위해서는 생각이 조금 필요하다. 범주는 대상Object과 사상Morphism으로 구성되어 있음을 기억하자.

처음에 이해하기 어려운 개념 중 하나는 모노이드에서 대상은 그다지 중요하지 않기 때문에 아무 것으로나 생각해도 된다는 것이다. 모노이드 범주에서 단일한 대상이 aa이든, Sojin\text{Sojin}이든, Eriri\text{Eriri}이든 큰 상관이 없다.

모노이드에서 중요한 것은 사상Morphism이다.

위에서 언급한 0을 포함하는 자연수 집합 N\mathbb{N}과 덧셈 ++으로 구성된 모노이드를 생각해 보자. 범주론에서는 집합 N\mathbb{N}의 각 원소 11, 22, ...를 모노이드를 구성하는 사상으로 본다. 그리고 원소 사이의 덧셈 연산 ++을 사상 사이의 합성으로 생각한다.

그래서 이 모노이드의 대상을 aa로 생각한다면 모노이드를 구성하는 사상들 1,2,1,,2,,\dots

1::aa2::aa... \begin{aligned} 1 & :: a \rightarrow a \ 2 & :: a \rightarrow a \ \end{aligned} \ ...

이 된다.

앞서서 모노이드의 연산은 사상 간의 합성과 같다고 언급하였다. 즉, 모노이드 연산 1+21 + 2는 사상 1122의 합성이 된다. 사상의 합성은 결합법칙Associativity을 만족하므로, 사상의 합성을 .,.,으로 나타낸다면 다음이 성립한다.

(1.2).3=1.(2.3)=1.2.3 (1 : . : 2) : . : 3 = 1 : . : (2 : . : 3) = 1 : . : 2 : . : 3

이는 모노이드 연산(여기서는 ++)이 결합법칙을 만족한다는 것과 일맥상통한다.

(1+2)+3=1+(2+3)=1+2+3 (1 + 2) + 3 = 1 + (2 + 3) = 1 + 2 + 3

또한 범주의 조건으로 항등 사상 id\text{id}가 있어야 함을 기억하자. 덧셈 모노이드에서 00을 항등 사상으로 생각하면 다음이 성립한다.

0.1=1.0=1 0 : . : 1 = 1 : . : 0 = 1

이것은 모노이드의 항등원이 가지고 있는 성질과 일치한다.

0+1=1+0=1 0 + 1 = 1 + 0 = 1

즉, 모노이드의 성질은 단일 대상의 범주가 가지는 성질로부터 자연스럽게 도출된다.

모노이드는 왜 좋은가

모노이드가 가지는 강력한 성질 중 하나는 결합법칙이 만족된다는 점이다. 결합법칙이 성립하면 연산을 처리하는 순서를 신경쓰지 않고 임의대로 연산을 묶어서 처리할 수 있게 된다. 예를 들어, 숫자 1,2,3,41,,2,,3,,4에 대해 덧셈 ++은 결합법칙을 만족시키므로

(((1+2)+3)+4)((1+2)+(3+4))(1+(2+(3+4))) \begin{aligned} (((1 + 2) + 3) + 4) \ ((1 + 2) + (3 + 4)) \ (1 + (2 + (3 + 4))) \end{aligned}

와 같이 어떤 순서로 연산을 먼저 실행하든 결과는 1010으로 같음이 보장된다. 처음부터 끝까지 순서대로 연산을 처리할 필요가 없는 것이다.

이에 따라 퀵소트Quicksort로 대표되는 분할 정복Divide and conquer 알고리즘을 적용하여 nn개의 원소에 대해 연산을 수행할 때 시간 복잡도를 O(n)O(n)에서 O(logn)O(\log n)까지 낮출 수 있다.

뿐만 아니라 큰 연산들을 분할하여 병렬 처리Parallel computing를 하는 데에 있어서도 무척 수월해진다. 연산이 수행되는 순서가 상관이 없어 병렬적으로 연산을 수행한 후 결과를 합치기만 하면 되기 때문이다. 이것은 프로그래밍에서 reduce 혹은 fold 연산과 관련이 깊다. (이때 reduce 연산의 초기값으로는 모노이드의 항등원을 제공하면 된다.)

정리

  1. 모노이드는 집합 MM과 이항 연산 \cdot이 있어서 항등원이 존재하고 결합법칙이 만족되는 특별한 구조이다.
  2. 모노이드의 예시로 0을 포함한 자연수 집합과 덧셈, 그리고 문자열과 문자열 연결 연산이 있다.
  3. 범주론에서 모노이드는 대상이 하나만 존재하는 범주를 가리킨다. 이때 사상을 집합의 원소로, 사상의 합성을 모노이드의 연산으로 본다.
  4. 모노이드를 사용하면 병렬 처리가 간단해져서 연산 수행의 시간 복잡도를 낮출 수 있다.