바인드(bind) 모나드 합성이 진짜 함수형일까?
Tags: monad, functional, haskell, mathematics
Published: 2020-05-01 17:07:21

---
title: 바인드(bind) 모나드 합성이 진짜 함수형일까?
published: true
description: 
tags: monad, functional, haskell, mathematics
---

모나드 합성이 과연 함수형일까 의심해본적이 있나요? 예를 하나 들어볼게요. 리스트 모나드를 이용해서 자연수의 변을 가진 삼각형(Integer Triangles)을 출력 해볼게요. 하스켈로 예를들어보면

```haskell
integerTriangles :: [(Int, Int, Int)]
integerTriangles = do
    z <- [1..]
    x <- [1..z]
    y <- [x..z]
    if x^2 + y^2 == z^2 then return (x, y, z)
                        else []

-- (3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17) ...
```

이 되겠죠 (모나드를 지원하는 다른 모든 함수형 언어들도 위와 상응하는 코드를 짤 수 있어요). 위 코드에서는 바인드(bind) 안에서 바인드를 재귀적으로 호출하고 있어요. syntactic sugar 를 제외하고 바인드의 재귀성을 좀 더 잘 나타내본다면.

```haskell
integerTriangles2 :: [(Int, Int, Int)]
integerTriangles2 =
    [1..] >>= \z ->
        [1..z] >>= \x ->
            [x..z] >>= \y ->
                if x^2 + y^2 == z^2 then [(x, y, z)]
                                    else []
```

이 되겠죠.

아무문제 없고, 많이 쓰이는 스타일이에요. 하지만 과연 이게 함수형이라고 말할 수 있을까요? 왜냐면 안쪽에 있는 함수들은 바깥에서 정의된 변수에 의존적인 컨텍스트(context)를 사용하고 있고, 컨텍스트에 따라 함수의 결과값이 달라지기 때문이에요. 다른말로 `z`가 변하면 `x`와 `y`도 변하니 함수형이라고 할 수 없는거죠.

함수형 프로그래밍 언어에서 위와같은 코드를 왜 용납하는걸까요? 편의를 위해 잠시 룰을 위반하는 걸까요?

그렇지 않아요. 왜 위와같은 코드가 함수형을 위반하는게 아닌지 설명해 드릴게요. 

# 배경지식

글을 읽기 앞서 몇가지 배경지식으로 요구할게요.

* 모나드의 기본적인 지식, 특히 `bind`와 `return`을 알고 계셔야 해요.
* 커리(Currying) 와 언커리(Uncurrying)을 알고 계셔야 해요.
* 기본적인 펑터(Functor)의 개념

# embrace : (a, m b) -> m(a, b)

우선 다음과 같은 변형(morphism/transformation)을 이해해야 해요.

{% katex %}
(a, m b) \rightarrow m(a, b)
{% endkatex %}

 여기서 `(x, y)`는 쌍(Pair 혹은 길이 2의 Tuple)이고, `m x`는 타입 `x` 를 파라메터로 가진 `m` 모나드 라는 뜻이에요. 이 변형은 둘중 하나는 모나드인 타입의 쌍을 받아서, 어떻게어떻게 그 타입에서 모나드를 벗겨낸 후 쌍 전체에 다시 씌워준다고 생각할 수 있어요. 예를들자면 `(String, [Int])`를 `[(String, Int)]`로 바꿔 준다고 볼 수 있죠. 이 변형을 어떻게 만드는지 알려드릴게요. 일단 `(x, m y)`부터 시작 할게요.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ai4e4zxs6bxpy6c35x15.jpeg)

모든 쌍 타입은 자연스럽게 두가지 변형을 동반해요. 바로 `first`와 `second`에요. 각각 쌍 타입의 첫번째, 두번째 오브젝트를 선택해서 바꿔주는 변형이에요.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/u3kuidkc738tke7vt1td.jpeg)

쌍 타입에서 자연스럽게 생기는 또다른 변형이 있어요. 바로 두가지 타입을 받아서 쌍 타입으로 만들어주는 생성자 에요. 수학에서는 파라메터를 두개를 받는 함수의 도메인을 집합의 곱으로 표현하니 저도 같은 심볼을 쓸게요.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/bhahqf1qwl9tz7gil7fx.jpeg)

이렇게 생성한 함수에 커리(Currying)을 합성해서 파라메터 한개짜리 함수로 바꿔볼게요.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/fa3znglhw17kdijdmx85.jpeg)

이제 이 함수에 `first` 로 얻은 `x`를 대입해볼게요.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/3kk8mtp2qq89p9ukxxv8.jpeg)

이제 `y`를 받는 함수가 생성이 됐어요. 하지만 우리는 `second`로 얻은 `m y` 밖에 없는데 어떡해야 할까요? 바로 `m` 모나드로부터 자연스럽게 생성된 `return : a -> m a` 을 단순히 왼쪽에 합성하는 것만으로 {% katex inline %} f : y \rightarrow (x, y){% endkatex%}를 {% katex inline %}g:y \rightarrow m (x, y){% endkatex %}로 같이 바꿀 수 있어요.

{% katex %}
g = \text{return} \cdot f
{% endkatex %}

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/otxut39s5g1lop0chdk0.jpeg)

이제 모나드 합성인 `bind`를 이용해서 `m y` 를 사용할 수 있게 됐죠

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/12zrv64qnvc1ecpwpu8u.jpeg)

이렇게 `(x, m y)` 를 `m(x, y)` 로 변형할 수 있어요. 모나드가 `y` 뿐만 아닌 `x`도 포함한다는 의미에서 이 변형을 `embrace`로 부를거에요. 수식으로 나타내보자면 다음과 같겠죠

{% katex %}
embrace : X \times mY \rightarrow m (X \times Y) \newline
embrace (x, my) = bind (return \circ curry \circ pair (x), my)
{% endkatex %}
# 함수형 모델

이제 우리는 재귀적 바인드 연산자 호출을 함수형 모델로 표현할 준비가 됐어요.

모나드 `m`의 `bind`의 signature는 다음과 같아요

{% katex %}
\text{bind} : m a \times (a \rightarrow m b) \rightarrow m b
{% endkatex %}

`bind`를 이용하면 {% katex inline %}m a{% endkatex %}와 {% katex inline %}a \rightarrow mb{% endkatex %}가 있다면 {% katex inline %}m b{% endkatex %}를 얻을 수 있죠. 그렇다면 한단계 더 나아가서, 다음과같은 세가지를 조합하는 `bind3`를 만들 수 있을까요?

{% katex %}
\text{bind3} : m a \times (a \rightarrow m b) \times (a \rightarrow b \rightarrow mc) \rightarrow m c
{% endkatex %}

> ###### 한번 퍼즐풀듯이 읽는걸 멈추고 펜과 종이를 들고 점과 화살표를 그려가면서 직접 유추해내 보세요.

이 세가지에서 시작해볼게요

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/xjh0mv35krrmp49g8jhx.jpeg)

커리를 이용해서 `plant`라는 일반변형을 하나 정의해볼게요

{% katex %}
\begin{aligned}
&\text{plant} : (a \rightarrow mb) \rightarrow (a \rightarrow (a, mb)) \\\\
&\text{plant}(f)(a) = (a, f(a))
\end{aligned}
{% endkatex %}

상당히 단순한 일반변형이에요. `a`를 받아서 바로 `mb`를 리턴하기 보단 파라메터로 받은 `a`도 `mb`와 같이 쌍으로 묶어서 리턴하는 함수에요. 단순하지만 굉장히 유용한 이 `plant`변형을 이용해서 다음과 같이 진행해볼게요.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/5dj4g5ooa2cysjlfvb0o.jpeg)

이제 아까 정의한 `embrace` 를 이용하면 {% katex inline %}f:a\rightarrow (a,mb){% endkatex%}을{% katex inline %}g:a\rightarrow m(a,b){% endkatex%} 으로 간단하게 변형할 수 있어요.

{% katex %}
g=\text{embrace} \cdot f
{% endkatex %}

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/r97auwg2bf3mcz7lmcy9.jpeg)

결과값으로 나온 함수와 {%katex inline%}m a{%endkatex%}를 조합해보면 {%katex inline%}m(a,b){%endkatex%}를 얻을 수 있어요.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/c9fbx265dpjzm86dgnxj.jpeg)

이제 이걸 남은 {%katex inline%}a \rightarrow b \rightarrow mc{%endkatex%} 와 합성하는 일만 남았어요. {%katex inline%}a \rightarrow b \rightarrow mc{%endkatex%}에 `uncurry`를 적용해볼게요.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/jvqdye406x2hmrizv4zx.jpeg)

이제 `bind`만 적용하면 {%katex inline%}mc{%endkatex%}를 얻을 수 있겠죠?

하.지.만

여기에 `plant`와 `embrace`를 적용 하고 그다음에 `bind`를 적용할 거에요. 왜냐면 지금 우리의 목적은 단순히 `m c`를 구하는것이 아닌 일반적인 함수형 모델을 만드는 것이기 때문이에요. 만약 여기서 `bind`를 사용해서 바로 `m c`를 구하고 나면 이 모델은 단순히 3차 `bind`까지만 구할 수 있는 모델이 되고 끝나버리는 거에요. 우리가 최초에 하고자 했던 자연수 삼각형에 우리가 지금 만들고 있는 모델을 적용하기 위해서는 4차, 즉 {%katex inline%}a \rightarrow b \rightarrow c \rightarrow md{%endkatex%}까지 가야 해요. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/8hq3pxwqnhm5dg1883di.jpeg)

우리가 알고싶은 `m c` 가 아닌 `m(a, b, c)`가 생겨버렸어요. 하지만 괜찮아요 `m(a, b, c)`에는 우리가 알고싶은 `m c`에 대한 정보가 모두 들어있기 때문이에요. 그저 튜플의 가장 마지막 값만 고르는 변형만 있음 돼요. `last` 변형을 한번 정의해볼게요.

{%katex%}
\begin{aligned}
&\text{last}: (a,b, \cdots z) \rightarrow z \\\\
&\text{last}(a,b, \cdots z) = z
\end{aligned}
{%endkatex%}

`m(a, b, c)` 에 위의 `last`를 적용한다면 `mc`를 얻을 수 있겠죠?

이제 똑같은 방법으로 `bind` 4단계 까지 확장해본다면 다음과 같아요.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/3mvul632v8ry83rptnhm.jpeg)

수식으로 나타내보면 다음과 같겠죠.

{% katex %}
t_i = (a,b,c,d \dots)_i \newline

T_n = \prod_{\mathclap{1\le i\le n}} t_i \newline

S_0 = m a \newline

S_{n+1} = \text{bind}(S_n, \text{embrace} \circ \text{plant} \circ \text{uncurry} (T_n \rightarrow t_{n+1}) )
{% endkatex %}

이제 최종적으로 우리가 얻고자 했던 자연수 삼각형에 이 모델을 대입해볼게요. 먼저 자연수 삼각형을 구하는 코드를 다시 한번 볼게요.

```haskell
naturalTriangles2 :: [(Int, Int, Int)]
naturalTriangles2 =
    [1..] >>= \z ->
        [1..z] >>= \x ->
            [x..z] >>= \y ->
                if x^2 + y^2 == z^2 then [(x, y, z)]
                                    else []
```

모델의 각각의 컴포넌트들은 코드에 다음과 같이 대응이 돼요.

| 모델 | 코드 |
| --- | --- |
| {%katex inline%} ma {%endkatex%} | `[1..]` |
| {%katex inline%} a \rightarrow mb {%endkatex%} | `\z -> [1..z]` |
| {%katex inline%} a \rightarrow b \rightarrow mc {%endkatex%} | `\z -> .. \x -> [x..z]` |
| {%katex inline%} a \rightarrow b \rightarrow c \rightarrow md {%endkatex%} | `\z -> .. \x -> .. \y -> ... [(x, y, z)]` |

우리가 컨텍스트라고 간주했던 바깥에서 정의된 변수들이 사실 같은 함수의, 밖이 아닌 안에서 정의된 파라메터들이 었던 거죠.

함수형같지 않던 재귀적 `bind`를 함수형 모델로 정의를 해보았습니다.