모나드(Monad)

계산기에 세 단계를 이어 놓았다고 합시다. f는 짝수를 반으로 나누고, g는 제곱수⁠(perfect square)⁠의 제곱근을 구하고, h는 10 이하인 수를 10에서 뺍니다. 셋 다 실패할 수 있습니다. 홀수는 반으로 나눌 수 없고, 6에는 정수⁠(integer)⁠ 제곱근이 없습니다. 실패할 수 있는 함수는 수를 돌려주는 대신 'Just 값' 또는 '없음'(Nothing)을 돌려줍니다. 그러면 f와 g를 그냥 합성할 수 없습니다. g는 수를 받는데 f는 Just 9나 Nothing을 돌려주니까요. 필요한 것은 풀칠입니다. 'Nothing이면 거기서 멈추고, Just x면 x를 꺼내 다음 함수에 넘긴다.' 이 풀칠로 이은 합성을 $f \mathbin{>\!=\!>} g$로 적고, 클라이슬리 합성⁠(Kleisli composition)⁠이라 부릅니다. 입력 n = , 맥락: , 처음 씨앗 = (상태 맥락에서만 씁니다).

같은 모양의 풀칠이 다른 맥락에서도 나옵니다.

• 실패(Maybe). 값이 하나 있거나 없습니다. 한 번 없음이 되면 뒤의 함수는 부르지도 않습니다.
• 여러 갈래(List). 함수가 가능한 답을 여러 개 돌려줍니다. 여기서 f는 n − 1과 n + 1을, g는 두 배와 세 배를 돌려주고, h는 짝수만 남깁니다. 풀칠은 '가능한 값마다 다음 함수를 적용한 뒤 결과 목록들을 하나로 이어 붙이기'이고, 빈 목록이 실패의 역할을 합니다.
• 상태(State). 함수가 값과 함께 숨은 상태를 읽고 바꿉니다. 여기서는 상태가 주사위를 굴리는 씨앗이고, f는 눈을 더하고, g는 눈을 곱하고, h는 눈을 뺍니다. 풀칠은 '앞 함수가 남긴 상태를 다음 함수에 넘기기'입니다. 같은 입력에 늘 같은 출력을 내는 순수한 함수로 무작위처럼 보이는 값을 얻으려면, 씨앗을 받아 새 씨앗을 돌려주어야 합니다.

세 경우 모두 재료가 같습니다. 값을 맥락에 담는 함자 T가 있습니다(Maybe A, List A, 그리고 '상태 s를 받아 값과 새 상태를 돌려주는 함수'). 평범한 값을 맥락에 넣는 $\eta_A: A\to TA$가 있습니다(Just x, [x], 상태를 건드리지 않고 x를 돌려주기. 프로그래밍에서는 return이라 부릅니다). 그리고 두 겹의 맥락을 한 겹으로 펴는 $\mu_A: T(TA)\to TA$가 있습니다(Just (Just x) → Just x, [[1, 2], [3]] → [1, 2, 3], '상태를 넘겨 가며 바깥 계산 다음 안쪽 계산을 실행하기'. join이라 부릅니다). 풀칠은 이것으로 정의됩니다.

$$f \mathbin{>\!=\!>} g \;=\; \mu\circ T(g)\circ f$$

f의 결과 안쪽 값에 g를 map하면(T(g)) 두 겹이 되고, μ가 그것을 폅니다. 그림의 위 줄과 아래 줄이 그 두 동작입니다. η와 μ는 모든 타입⁠(type)⁠ A에 대해 똑같은 규칙으로 작동하는 자연 변환⁠(natural transformation)⁠이어야 합니다.

(T, η, μ)가 모나드(monad)이려면 법칙 세 개가 필요합니다. 풀칠로 적으면

$$\eta \mathbin{>\!=\!>} f = f,\qquad f \mathbin{>\!=\!>} \eta = f,\qquad (f \mathbin{>\!=\!>} g) \mathbin{>\!=\!>} h = f \mathbin{>\!=\!>} (g \mathbin{>\!=\!>} h)$$

입니다. 앞의 둘은 '아무것도 하지 않는 단계를 끼워도 결과가 같다', 셋째는 '어디서 끊어 묶어도 결과가 같다'입니다. 곧 A → TB 모양의 함수들을 화살표로 삼고 >=>를 합성으로 삼으면 범주가 된다는 것이고(클라이슬리 범주⁠, Kleisli category⁠), 세 법칙은 범주의 항등 화살표⁠(identity arrow)⁠ 법칙과 결합법칙 그 자체입니다. 이 법칙이 왜 필요한지는 프로그램을 고칠 때 드러납니다. 긴 파이프라인의 일부를 도우미 함수로 묶어 내도 뜻이 바뀌지 않는다는 것이 결합법칙이고, 이것이 없으면 코드를 정리할 때마다 동작이 바뀔 위험이 생깁니다. 같은 법칙을 μ와 η로 적으면 $\mu\circ T\mu = \mu\circ\mu_T$(세 겹을 안쪽부터 펴든 바깥쪽부터 펴든 같다), $\mu\circ\eta_T = \mu\circ T\eta = \mathrm{id}$(한 겹 씌운 뒤 펴면 제자리)입니다.

'모나드는 자기 함자 범주⁠(functor category)⁠의 모노이드⁠(monoid)⁠일 뿐'이라는 말이 유명합니다. 매클레인의 1971년 교과서에 나오는 문장인데, 정확한 뜻은 이렇습니다. 범주 𝒞에서 𝒞로 가는 함자들을 대상으로, 자연 변환들을 화살표로 하는 범주를 생각하고, 두 함자를 '곱하는' 방법으로 합성 $T\circ T$를, '1'로 항등 함자를 씁니다. 그러면 μ: T∘T ⇒ T가 곱셈, η: Id ⇒ T가 단위원⁠(unit circle)⁠ 노릇을 하고, 위의 두 법칙은 모노이드의 결합법칙 $(ab)c = a(bc)$와 항등원 법칙 $ea = a = ae$를 화살표로 적은 그림과 똑같습니다. 이것은 비유가 아니라 정의입니다. 모노이드는 집합⁠(set)⁠ M, 곱셈 함수 M × M → M, 단위 함수 1 → M(원소⁠(element)⁠ 하나짜리 집합에서 e를 고르는 함수)으로 원소 없이 적을 수 있습니다. 여기서 곱집합 × 자리에 함자의 합성 ∘를, 1 자리에 항등 함자를 넣으면 모나드의 정의가 글자 그대로 나옵니다(모노이드 범주의 모노이드 대상⁠(monoid object)⁠). 다만 원소와 연산을 가진 보통의 모노이드는 아닙니다. T는 집합이 아니고, μ는 두 원소를 곱하는 연산이 아니라 두 겹을 펴는 변환입니다. 보통의 모노이드가 글자 그대로 들어가는 모나드도 있습니다. 값과 함께 기록을 남기는 Writer 모나드 TA = A × W에서는 기록 W가 모노이드여야 하고, 풀칠은 두 단계의 기록을 모노이드 연산으로 이어 붙이며, 모나드 법칙은 W의 결합법칙과 항등원에서 곧바로 나옵니다.

모나드는 어디서 올까요? 수반 함자⁠(adjoint functor)⁠ L ⊣ R이 있으면 T = R∘L은 모나드입니다. η는 수반의 단위이고, μ는 가운데 두 겹 LR을 쌍대 단위⁠(counit)⁠로 줄인 것입니다. 목록 모나드는 '집합 → 자유 모노이드⁠(free monoid)⁠ → 다시 집합'에서 나오고(μ인 이어 붙이기가 자유 모노이드의 곱셈), Maybe는 집합에 점 하나를 덧붙여 '기준점이 있는 집합'을 만드는 구성과 그 기준점을 잊는 함자⁠(forgetful functor)⁠의 수반에서, 상태 모나드 $S\to A\times S$는 커링⁠(currying)⁠의 수반 $(-\times S)\dashv(-)^S$에서 나옵니다. 거꾸로 모든 모나드가 어떤 수반에서 나온다는 것을 1965년 하인리히 클라이슬리가, 같은 해 따로 에일렌베르크와 존 무어가 보였습니다. 확률⁠(probability)⁠에도 모나드가 있습니다. 각 단계가 값 하나 대신 확률 분포를 돌려주면, 풀칠은 '가능한 중간값 b마다 P(b) × P(c | b)를 더하기', 곧 전확률 공식입니다(조건부 확률⁠, conditional probability⁠). 상태가 유한한 마르코프 연쇄⁠(Markov chain)⁠에서는 이 풀칠이 전이 행렬⁠(transition matrix)⁠의 곱이고, 결합법칙은 여러 걸음의 전이 확률⁠(transition probability)⁠을 어디서 끊어 계산해도 같다는 채프먼–콜모고로프 방정식입니다.

모나드는 1950–60년대 호몰로지 대수에서 '표준 구성', '트리플' 같은 이름으로 먼저 나타났습니다. 프로그래밍으로 온 것은 1989년 에우제니오 모지가 예외, 여러 갈래, 상태, 입출력 같은 '계산의 효과'를 모두 클라이슬리 범주로 다룰 수 있음을 보이면서입니다. 필립 와들러가 1990년대 초 이것을 함수형 프로그래밍의 도구로 소개했고, 1996년 Haskell 1.3이 입출력을 모나드로 하게 되었습니다. 두 가지 오해를 짚어 둡니다. 모나드는 '값을 담는 상자'가 아닙니다. 상태 모나드의 값은 상자가 아니라 함수입니다. 모나드의 본질은 담는 방식이 아니라 풀칠이 지키는 법칙입니다. 또 두 모나드를 합치는 방법은 하나로 정해지지 않습니다. 두 함자를 그냥 합성한 T∘S가 모나드가 된다는 보장부터 없고, 된다 해도 방법이 여럿입니다. '갈래마다 따로 실패할 수 있는 계산'과 '한 갈래라도 실패하면 전체가 실패하는 계산'은 다른 것이고, Maybe와 List 가운데 어느 쪽을 바깥에 두느냐로 갈립니다.

이어지는 곳. 모나드의 법칙은 모노이드의 결합법칙과 항등원이 함자와 자연 변환의 수준에서 다시 나타난 것이고, 클라이슬리 합성이 이루는 것은 또 하나의 범주입니다. 모나드가 어디서 오는지는 수반 함자가, 상태 모나드가 왜 함수 모양인지는 데카르트 닫힌 범주⁠(cartesian closed category)⁠의 커링이 설명합니다. 확률 분포의 모나드는 조건부 확률과 마르코프 연쇄를 한 가지 합성으로 보게 하고, 씨앗을 넘겨 가며 난수를 만드는 방법은 몬테카를로 방법⁠(Monte Carlo method)⁠에서 같은 실험을 그대로 다시 돌릴 수 있게 해 줍니다. 순수한 계산과 효과를 타입으로 나누는 설계는 타입 이론⁠(type theory)⁠과 람다 계산⁠(lambda calculus)⁠에서, 모나드를 쓰는 코드의 타입을 기계가 알아내는 일은 타입 추론⁠(type inference)⁠에서 이어집니다. 순서에서 모나드는 늘리기만 하고 두 번 해도 한 번과 같은 닫힘 연산⁠(closure operator)⁠이고 갈루아 연결⁠(Galois connection)⁠을 한 바퀴 돌면 늘 하나 나오며, '모나드는 자기 함자 범주의 모노이드'라고 할 때의 범주는 모노이드 범주입니다. 화살표를 뒤집은 쌍대 모나드⁠(comonad)⁠는 선형 논리⁠(linear logic)⁠의 !를 해석합니다.