모노이드(Monoid)

문자열 '가'와 '나'를 이어 붙이면 '가나'입니다. 이어 붙이기는 순서가 중요해서 '가'+'나'와 '나'+'가'는 다르지만, 괄호는 중요하지 않습니다. ('가'+'나')+'다'와 '가'+('나'+'다')는 모두 '가나다'입니다. 그리고 빈 문자열 ''은 어디에 붙여도 아무것도 바꾸지 않습니다. 이 두 성질만 가진 구조가 모노이드(monoid)입니다. 집합 M과 M 위의 연산 ·, M의 원소⁠(element)⁠ e가 있어서 M의 모든 a, b, c에 대해

$$(a\cdot b)\cdot c = a\cdot(b\cdot c)\quad\text{(결합법칙)},\qquad e\cdot a = a = a\cdot e\quad\text{(항등원)}$$

가 성립하면 (M, ·, e)를 모노이드라 합니다. 군과 달리 되돌리는 원소(역원⁠, inverse element⁠)는 요구하지 않습니다. 이어 붙인 문자열을 원래대로 떼어 낼 '음의 문자열'은 없으니까요. 교환법칙⁠(commutative law)⁠도 요구하지 않습니다.

모노이드는 어디에나 있습니다. 0 이상의 정수⁠(integer)⁠와 덧셈(항등원 0), 자연수⁠(natural number)⁠와 곱셈(항등원 1), 참·거짓과 AND(항등원 참), 참·거짓과 OR(항등원 거짓), 0 이상의 정수와 최댓값(항등원 0. 실수⁠(real number)⁠ 전체에서는 가장 작은 수가 없으므로 −∞를 덧붙여야 항등원이 생깁니다), n×n 행렬⁠(matrix)⁠과 행렬의 곱(항등원 단위행렬⁠(identity matrix)⁠), 집합 X에서 X로 가는 함수들과 합성(항등원 항등 함수)이 모두 모노이드입니다. 아닌 것도 있습니다. 뺄셈은 (5 − 3) − 1 = 1이지만 5 − (3 − 1) = 3이라 결합법칙이 깨집니다. 두 수의 평균⁠(mean)⁠도 (2와 4의 평균)과 8의 평균은 5.5인데 2와 (4와 8의 평균)의 평균은 4입니다. 양의 정수와 덧셈은 결합법칙은 지키지만 항등원 0이 없습니다. 결합법칙만 지키는 이런 구조를 반군(semigroup)이라 합니다. 아래 표에서 연산을 바꿔 가며 두 조건을 직접 확인해 보세요. 연산은 , a = , b = , c = 입니다.

항등원은 있으면 하나뿐입니다. e와 e′이 둘 다 항등원이면 $e = e\cdot e' = e'$이기 때문입니다. 앞의 등호는 e′이 항등원이라서, 뒤의 등호는 e가 항등원이라서 성립합니다. 결합법칙이 주는 것은 더 큽니다. 괄호를 어디에 치든 결과가 같으니 $a_1\cdot a_2\cdots a_n$을 괄호 없이 써도 뜻이 하나로 정해집니다. 네 원소를 곱하는 괄호 치기는 카탈랑 수⁠(Catalan number)⁠만큼, 곧 5가지가 있는데, 세 원소의 결합법칙을 되풀이해 적용하면 이 다섯이 모두 같아집니다. 항등원은 빈 곱의 답입니다. 아무것도 더하지 않으면 0, 아무것도 곱하지 않으면 1, 아무것도 AND하지 않으면 참입니다. 마지막 것은 '빈 집합의 모든 원소는 어떤 조건이든 만족한다'는 규칙과 같은 이야기입니다.

결합법칙은 계산을 나누어 맡길 수 있는 근거이기도 합니다. 아래는 여덟 개를 한 줄로 차례차례 계산하는 방식과, 둘씩 짝지어 나무 모양으로 계산하는 방식을 견준 것입니다. 연산 , 계산 모양 .

차례로 계산하면 일곱 번을 차례로 기다려야 하지만, 나무 모양이면 같은 높이의 계산을 동시에 할 수 있어 세 단계로 끝납니다. 연산 횟수는 두 방식 모두 일곱 번이고, 달라지는 것은 차례로 기다려야 하는 단계 수입니다. n개라면 n − 1단계 대 $\lceil\log_2 n\rceil$단계입니다(분할 정복⁠(divide and conquer)⁠, 점근 표기법⁠(asymptotic notation)⁠). 수백만 개의 수를 더할 때 여러 기계가 조각을 나눠 더한 뒤 그 결과를 다시 더해도 되는 것은 덧셈이 결합법칙을 지키기 때문이고, 빈 조각은 항등원 0을 내놓으면 됩니다. 결합법칙이 없으면 두 방식의 답이 달라져서 이렇게 나눌 수 없습니다. 컴퓨터의 부동소수점⁠(floating point)⁠ 덧셈은 반올림 때문에 결합법칙이 아주 조금 어긋나므로, 나누는 방식에 따라 마지막 자리가 달라질 수 있습니다.

모노이드 사이의 준동형⁠(homomorphism)⁠은 연산과 항등원을 지키는 함수, 곧 $\varphi(a\cdot b) = \varphi(a)\cdot\varphi(b)$, $\varphi(e) = e$인 함수입니다. 문자열의 길이는 이어 붙이기를 덧셈으로 옮깁니다(len(uv) = len u + len v, len '' = 0). 로그는 양수의 곱셈을 덧셈으로 옮기고(log xy = log x + log y, log 1 = 0), 행렬식⁠(determinant)⁠은 행렬의 곱⁠(matrix multiplication)⁠을 수의 곱으로 옮깁니다(det AB = det A · det B, det I = 1).

알파벳 A의 글자로 만든 문자열 전체 $A^*$는 '가장 자유로운' 모노이드입니다. 글자마다 아무 모노이드 M의 원소를 하나씩 정해 주면(함수 $f: A\to M$), 그것을 연장하는 준동형 $A^*\to M$이 정확히 하나 있습니다. 문자열 $a_1 a_2\cdots a_n$을 $f(a_1)\cdot f(a_2)\cdots f(a_n)$으로 보내는 것입니다. 예를 들어 M을 정수와 덧셈으로 두고 '('를 +1로, ')'를 −1로 보내면 이 준동형은 괄호 문자열의 '여는 괄호 수 − 닫는 괄호 수'를 셉니다. 준동형이 많아야 하나인 까닭은 문자열이 글자들의 곱이라 글자가 가는 곳이 정해지면 나머지가 모두 정해지기 때문이고, 적어도 하나 있는 까닭은 문자열 사이에 결합법칙과 빈 문자열의 성질 말고는 아무 관계도 없기 때문입니다. 이 '하나뿐인 연장'이 보편 성질⁠(universal property)⁠의 한 예이고, 자유 모노이드⁠(free monoid)⁠와 '연산을 잊는' 함자⁠(functor)⁠가 이루는 짝이 수반 함자⁠(adjoint functor)⁠이며, 그 짝에서 목록(List) 모나드⁠(monad)⁠가 나옵니다. 함수형 프로그래밍의 foldMap이 바로 이 준동형입니다.

범주의 눈으로 보면 모노이드는 대상이 하나뿐인 범주입니다. 대상 ★ 하나에 원소마다 화살표 ★ → ★ 하나를 두고, 합성을 연산으로, 항등 화살표⁠(identity arrow)⁠를 e로 두면 범주의 두 법칙(결합법칙, 항등 화살표)이 모노이드의 두 조건과 글자 그대로 같습니다. 모노이드 준동형은 이런 범주 사이의 함자이고, 거꾸로 어떤 범주에서든 한 대상 A에서 A로 가는 화살표들은 모노이드를 이룹니다. 그래서 범주를 '대상이 여럿이라 끝이 맞는 것끼리만 곱할 수 있는 모노이드'로 볼 수도 있습니다. 크기가 제각각인 행렬 전체가 꼭 그렇습니다. 같은 모노이드는 기계에서도 나옵니다. 유한 오토마톤⁠(finite automaton)⁠에서 글자 하나는 상태에서 상태로 가는 함수이고 문자열은 그 함수들의 합성이므로, 문자열들이 만드는 함수 전체가 모노이드를 이루고 상태가 유한하니 이 모노이드도 유한합니다. 거꾸로도 됩니다. 어떤 언어가 정규 언어⁠(regular language)⁠일 필요충분조건은, 문자열을 어떤 유한 모노이드로 보내는 준동형이 있어서 그 값만 보고 문자열이 언어에 속하는지 판정할 수 있는 것입니다.

이어지는 곳. 역원까지 있으면 군이 되어 대칭을 다룰 수 있습니다. 괄호 치기의 가짓수는 카탈랑 수로, 결합법칙 덕분에 나눠 계산하는 방법은 분할 정복으로 이어집니다. 대상이 하나인 범주라는 관점은 범주론⁠(category theory)⁠을 '여러 대상의 모노이드'로 읽게 해 주고, 모노이드의 결합법칙과 항등원이 한 층 위에서 다시 나타나는 것이 모나드라서 모나드의 법칙이 왜 그 모양인지가 여기서 보입니다. 자유 모노이드에서 시작하는 짝은 수반 함자의 가장 기본적인 예이고, 문자열 모노이드는 유한 오토마톤과 정규 표현식⁠(regular expression)⁠의 대수적 뼈대입니다. 곱을 합으로 바꾸는 준동형 로그와 넓이⁠(area)⁠의 배율을 곱으로 모으는 행렬식은 계산을 쉬운 모노이드로 옮기는 도구입니다. 문자열을 모노이드 연산으로 접는 자유 모노이드의 '하나뿐인 연장'은 시작 대수의 fold가 마침 모노이드 준동형이 되는 경우이고, 원소 대신 대상들을 모노이드처럼 곱하는 범주가 모노이드 범주입니다.