바인드(bind) 모나드 합성이 진짜 함수형일까?

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

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 를 제외하고 바인드의 재귀성을 좀 더 잘 나타내본다면.

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)을 이해해야 해요.

$$(a, m b) \rightarrow m(a, b)$$

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

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

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

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

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

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

$$g = \text{return} \cdot f$$

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

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

$$embrace : X \times mY \rightarrow m (X \times Y) \newline embrace (x, my) = bind (return \circ curry \circ pair (x), my)$$

함수형 모델

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

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

$$\text{bind} : m a \times (a \rightarrow m b) \rightarrow m b$$

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

$$\text{bind3} : m a \times (a \rightarrow m b) \times (a \rightarrow b \rightarrow mc) \rightarrow m c$$

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

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

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

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

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

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

$$g=\text{embrace} \cdot f$$

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

이제 이걸 남은 $a \rightarrow b \rightarrow mc$ 와 합성하는 일만 남았어요. $a \rightarrow b \rightarrow mc$ 에 uncurry를 적용해볼게요.

이제 bind만 적용하면 $mc$ 를 얻을 수 있겠죠?

하.지.만

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

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

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

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

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

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

$$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}) )$$

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

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 []

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

모델	코드
$ma$	[1..]
$a \rightarrow mb$	\z -> [1..z]
$a \rightarrow b \rightarrow mc$	\z -> .. \x -> [x..z]
$a \rightarrow b \rightarrow c \rightarrow md$	\z -> .. \x -> .. \y -> ... [(x, y, z)]

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

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