Monad 4 - Distributive Law
Before starting
이 글은 3편에서 다뤘던 내용 중, 모나드 간의 분배법칙에 관한 보충 설명이다. 굳이 해당 내용을 글 하나로 뺄 정도로, 꽤나 길고 복잡한 내용이 섞여 있다.
Functor, Applicative의 합성
먼저, 3편에서는 Functor와 Applicative는 합성에 대해 닫혀있다고 했는데, 왜 그런지부터 확인해보자.
Functor의 경우, 두 Functor F, G를 합성해도 다음과 같이 Functor를 구현할 수 있다.
1
2
fmap :: (a -> b) -> F(G a) -> F(G b)
fmap f = fmap_F (fmap_G f)
즉, fmap의 인자로 주어진, 값 변환 함수 a -> b를 안쪽까지 밀어넣기만 하면 되므로, Functor는 합성 연산에 대해서 닫혀있음을 알 수 있다.
Applicative의 경우, 두 Applicative F, G를 합성해도 다음과 같이 Applicative를 구현할 수 있다.
1
2
3
4
5
pure :: a -> F(G a)
pure = pure_F . pure_G
(<*>) :: F(G (a ->b)) -> F(G a) -> F(G b)
(<*>) f x = fmap_F (<*>_G) f <*>_F x
여기도 같은 원리로, 각각의 레이어에서 pure와 Apply를 순차적으로 적용하면 되니 Applicative도 합성 연산에 대해서 닫혀있다.
이러한 구현 외에도, Functor와 Applicative는 둘 다 컨텍스트 내부의 값을 변환할 수만 있으면 되기 때문에, 즉 필요한 연산이 단방향이기 때문에 그냥 순차적으로 적용하면 되는 것이다.
What about Monad?
Join
그럼 모나드에선 어떻게 바뀔까? 모나드에 대한 합성을 정의하기 전에, join함수를 살펴봐야 한다.
우리는 여태 모나드를 return과 Bind로 정의했었다. 그러나 사실, 수학적으로는 return과 join으로 정의된다. join은 다음과 같이 정의된 함수다.
1
join :: M (M a) -> M a
즉, 2중첩으로 된 모나드에서 중첩을 한 개 지워내는 함수이다. 모나드는 Functor이기 때문에 fmap이 제공된다. 그런데 fmap을 반복적으로 적용하다보면 컨텍스트가 계속 중첩되게 된다. fmap은 컨텍스트를 추가만 하기 때문이다. 그래서 컨텍스트를 유지하면서 계산을 하기 위해서는 이 중첩된 컨텍스트를 제거할 방법이 필요하다. 그렇게 해야지만 비로소 계산을 자유롭게 할 수 있어 모나드라고 부를 수 있게 된다.
그리고 우리가 흔히 알고 있는 Bind는 사실 fmap과 join으로 구현이 가능하다.
1
m >>= f = join (fmap f m)
당연하지만, 컨텍스트가 몇 번 중첩되든 한 겹만 남기고 제거하기 위해서는 지울 때도 한 겹씩 제거해야만 한다. 그렇기 때문에 join함수는 반드시 1개 단위로 컨텍스트를 제거해야 한다.
Monad Composition
그럼 이제 모나드의 합성을 생각해보자.
1
2
3
4
return :: a -> M(N a)
return = return_M . return_N
join :: M(N(M(N a))) -> M(N a)
우선, 위에서의 고찰을 통해 Bind 대신 join에 대해서만 생각해도 충분하다. 그리고 return의 경우 합성이 매우 잘 된다. 사실 Applicative의 pure와 동일해서 더 볼 필요도 없다.
문제는 join인데, M(N(M(N a))) -> M(N a)를 구현해야 하고, 우리가 가진건 다음의 두 함수 뿐이다.
1
2
join_M :: M(M a) -> M a
join_N :: N(N a) -> N a
이걸 사용해서 줄이기 위해서는 N(M a) -> M(N a)가 필요하다. 이게 있어야지 M(N(M(N a))) -> M(M(N(N a))) -> M(N(N a)) -> M(N a)의 순서를 거쳐 M . N에 대한 join을 구현할 수 있다.
즉, 모나드의 합성을 정의하려면 함수 N(M a) -> M(N a)가 필요하며, 이는 분배법칙에 해당한다. 결국 모나드에서 분배법칙이 적용되느냐가 모나드의 합성이 가능한지로 귀결된다.
Distributive Law between Monads
근데 모나드 간의 분배법칙이 성립하는지 아닌지는 직관적으로 알긴 너무 어렵다. 그래서 실제로 어떻게 증명되었나를 살펴볼 건데, 여기서는 2006년에 발표된 Varacca & Winskel의 논문 Distributing Probability over Non-determinism에서 제시된 방법을 소개할 것이다.
어떤 것이 불가능함을 증명하는 가장 대표적인 방법은 귀류법이다. 또한 불가능을 증명할 때에는 반례를 하나 찾기만 해도 충분하다. 이들의 증명은 여기서 출발한다.
논의를 시작하기 앞서, $\lambda: D \circ P \Rightarrow P \circ D$라는 분배법칙이 성립하기 위해서는 다음의 4개의 조건을 모두 만족해야 한다는 공리가 존재한다.
- A1: $\lambda \circ \eta^D_{P(X)} = P(\eta^D_X)$
- A2: $\lambda \circ D(\eta^P_X) = \eta^P_{D(X)}$
- A3: $\lambda \circ \mu^D_{P(X)} = P(\mu^D_X) \circ \lambda_{D(X)} \circ D(\lambda_X)$
- A4: $\lambda \circ D(\mu^P_X) = \mu^P_{D(X)} \circ (P(\lambda_X)) \circ \lambda_{P(X)}$
여기서 $\eta$는 각 모나드의 unit을 나타내는 자연 변환이고, $\mu$는 모나드의 곱셈을 의미하는 자연 변환이다. 위의 4가지 공리는 각각 D의 unit 보존, P의 unit 보존, D의 곱셈 보존, P의 곱셈 보존을 의미한다.
즉, 두 모나드를 적절히 찾아서 이들은 분배법칙이 성립하지 않는다는 것을 증명하면 되는 것이고, 이들 간의 분배법칙이 성립하지 않는다는 것을 증명하기 위해 귀류법을 적용하여 일단 된다고 가정하고 모순을 이끌어낼 것이다.
여기서 정한 두 개의 모나드는 다음과 같다.
- Finite Nonempty Powerset Monad P: 확률과 무관하게 시스템이 여러 선택지 중 하나를 선택하는 상황
- Finite Valuation Monad D: $p$의 확률로 A를, $(1-p)$의 확률로 B를 선택하는 등의 확률적 상황
즉, 이들 사이의 분배법칙이 성립한다는 소리는, “집합들의 확률분포”를 “확률분포들의 집합”으로 바꿀 수 있다는 이야기이다. 그럼 이러한 조건을 만족하는 분배법칙 $\lambda$가 무엇을 만족해야 하는지 살펴보자.
Step 1
위의 공리 A1에 의해서, 집합 $S$에서 확률이 1이 되는 point mass $\delta_S$에 대해 $\lambda$는 다음을 만족해야 한다.
\[\lambda_X(\delta_S) = \lbrace \delta_x \mid x \in S \rbrace\]예를 들어 $S = \lbrace a, b \rbrace$라면 $\lambda_X(\delta_{\lbrace a, b \rbrace}) = \lbrace \delta_a, \delta_b \rbrace$가 된다.
또한, A2에 의해 임의의 분포 $\mu \in D(X)$를 각 원소의 Singleton으로 끌어올린 분포에 대해서 다음이 성립한다.
\[\lambda_X \left(\sum_x \mu(x) \cdot \delta_{\lbrace x \rbrace} \right) = \lbrace \mu \rbrace\]즉, $x \rightarrow \lbrace x \rbrace$로 보낸 분포는 반드시 $\lbrace \mu \rbrace$라는 단원소 집합으로 가야만 한다.
Step 2
그럼 이제 $X = \lbrace a, b, c, d \rbrace$라고 하고, 다음의 원소를 생각해보자.
\[v = \dfrac{1}{2} \delta_{\lbrace a, b \rbrace} + \dfrac{1}{2} \delta_{\lbrace c, d \rbrace} \in D(P(X))\]그리고 다음의 3가지 함수를 정의하자.
- $f: a, b \rightarrow u \mid c, d \rightarrow v$ ($\lbrace a, b \rbrace \mid \lbrace c, d \rbrace$ 분할)
- $g: a, c \rightarrow u \mid b, d \rightarrow v$ ($\lbrace a, c \rbrace \mid \lbrace b, d \rbrace$ 분할)
- $h: a, d \rightarrow u \mid b, c \rightarrow v$ ($\lbrace a, d \rbrace \mid \lbrace b, c \rbrace$ 분할)
이제 $f$에 대해서 좀 더 파헤쳐보자. $f$는 다음을 만족하게 된다.
\[D(P(f))(v) = \dfrac{1}{2} \delta_{\lbrace u \rbrace} + \dfrac{1}{2} \delta_{\lbrace v \rbrace}\]그리고 공리 A2에 의해,
\[\lambda_{\lbrace u, v \rbrace} \left(\dfrac{1}{2} \delta_{\lbrace u \rbrace} + \dfrac{1}{2} \delta_{\lbrace v \rbrace} \right) = \left\lbrace \dfrac{1}{2}\delta_u + \dfrac{1}{2}\delta_v \right\rbrace\]위의 내용에 더해 자연성 조건인 $P(D(f)) \lambda_X = \lambda_{\lbrace u, v \rbrace} D(P(f))$로부터 다음을 얻을 수 있다.
\[P(D(f))(\lambda_X(v)) = \left\lbrace \dfrac{1}{2}\delta_u + \dfrac{1}{2}\delta_v \right\rbrace\]즉, $\lambda_X(v)$ 안의 모든 분포 $\mu$는 $D(f)(\mu) = \dfrac{1}{2}\delta_u + \dfrac{1}{2}\delta_v$를 만족해야 한다. 그리고 이는 곧 $\mu$는 $\lbrace a, b \rbrace$에 $\dfrac{1}{2}$, $\lbrace c, d \rbrace$에 $\dfrac{1}{2}$의 확률을 부여해야 함을 알 수 있다.
위의 내용을 $g$, $h$에 대해서도 적용하면 최종적으로 $\lambda_X(v)$ 안의 모든 $\mu$는 다음의 조건을 만족해야 한다.
- $\lbrace a, b \rbrace$에 $\dfrac{1}{2}$, $\lbrace c, d \rbrace$에 $\dfrac{1}{2}$ 부여
- $\lbrace a, c \rbrace$에 $\dfrac{1}{2}$, $\lbrace b, d \rbrace$에 $\dfrac{1}{2}$ 부여
- $\lbrace a, d \rbrace$에 $\dfrac{1}{2}$, $\lbrace b, c \rbrace$에 $\dfrac{1}{2}$ 부여
그리고 $\mu(a) = p$, $\mu(b) = q$, $\mu(c) = r$, $\mu(d) = s$라고 하면,
- From $f$ : $p + q = \dfrac{1}{2}$, $r + s = \dfrac{1}{2}$
- From $g$ : $p + r = \dfrac{1}{2}$, $q + s = \dfrac{1}{2}$
- From $h$ : $p + s = \dfrac{1}{2}$, $q + r = \dfrac{1}{2}$
위 연립방정식의 해는 $p = q = r = s = \dfrac{1}{4}$가 유일하다.
Step 3
우선 공리 A1에 의해 다음이 성립한다.
- $\lambda_X(\delta_{\lbrace a, b \rbrace}) = \lbrace \delta_a, \delta_b \rbrace$
- $\lambda_X(\delta_{\lbrace c, d \rbrace}) = \lbrace \delta_c, \delta_d \rbrace$
이제 공리 A4를 $v$에 적용해보자. 공리 A4의 의미는 “혼합 분포를 $\lambda$로 변환할 때, 각 구성 요소를 먼저 변환한 결과들로부터 만들어져야 한다.”는 뜻이다. 그리고 $v = \dfrac{1}{2} \delta_{\lbrace a, b \rbrace} + \dfrac{1}{2} \delta_{\lbrace c, d \rbrace}$로 정의되었었다.
즉, $\lambda_X(v)$의 원소들은 반드시 $\lbrace \delta_a, \delta_b \rbrace$에서 한 개, 그리고 $\lbrace \delta_c, \delta_d \rbrace$에서 한 개를 골라 이 둘을 각각 $\dfrac{1}{2}$의 가중치로 결합한 형태여야 한다.
\[\dfrac{1}{2}\delta_a + \dfrac{1}{2}\delta_c, \quad \dfrac{1}{2}\delta_a + \dfrac{1}{2}\delta_d, \quad \dfrac{1}{2}\delta_b + \dfrac{1}{2}\delta_c, \quad \dfrac{1}{2}\delta_b + \dfrac{1}{2}\delta_d\]즉 위의 4가지 형태들 중 어느 하나로만 가능하다. 그런데 이들은 어느 형태든 정확히 2개의 점에만 질량을 부여한 형태다. 이는 위의 4가지 점에 모두 균등하게 분포되어야 한다는 Step2의 결과와 모순이 생긴다.
이로써 $\lambda$는 모든 공리와 자연성 조건을 동시에 만족시킬 수 없으며, 이는 곧 두 모나드 P와 D 사이에는 분배법칙이 성립하지 않는다는 이야기이다. 또한 분배법칙이 성립되지 않는 두 모나드가 존재함이 증명되었으므로, 임의의 두 모나드 간에 분배법칙은 항상 성립하는 것이 아니라는 것이 증명되었다.
Generalization
사실 위의 증명은 모나드 간의 분배법칙이 성립하지 않을 수 있다는 것을 보이는 데에는 성공했으나, 다른 모나드 쌍에 대해서는 아무것도 말해주지 않는다. 그리고 실제로 그 이후로도 개별 쌍에 대해서만 따로따로 증명을 해서 어떤 쌍은 되고 어떤 쌍은 안되는지를 하나하나 찾아낼 수 밖에 없었다.
즉, 임의의 두 모나드 쌍에 대해서 일반화시킬 방법이 필요하다. 이는 2020년에 이르러서야 Zwart & Marsden에 의해 정립되었으며, 그 증명은 그들의 논문 No-Go Theorems for Distributive Laws에 정리되어 있다.
그러나 위의 내용은 Universal Algebra를 알아야 읽을 수 있을 정도로 난이도가 높아서, 여기서 별도로 다루진 않을 것이다. 사실 나도 수학 쪽을 그리 잘 아는건 아니라서 굳이 내용을 확인해보진 않았다.
여담으로 이를 통해 모나드의 분배법칙이 성립하기 위한 충분조건을 찾아냈으나, 필요충분조건은 아직 밝혀지지 않았다고 한다. 그래도 “이 조건이면 불가능하다”라도 찾은게 어딘가.