Ingun 전인건

Posted on May 1, 2020 • Edited on Jul 28

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

#monad #functional #haskell #mathematics

모나드 합성이 과연 함수형일까 의심해본적이 있나요? 예를 하나 들어볼게요. 리스트 모나드를 이용해서 자연수의 변을 가진 삼각형(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를 함수형 모델로 정의를 해보았습니다.

DEV Community

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

배경지식

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

함수형 모델

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

Top comments (0)

Read next

Controle de estoque Supermercado

2D Game Menu with Godot4

Fixing the 'MySQL Module Shutting Down Unexpectedly' Error in XAMPP: Step-by-Step Guide

Creating Figma Unions