PBT로 FP 법칙 확인해보기 - Monad

Monad

Functor가 map을 가지고 있는 자료 구조들을 일반화한 특질인 것 처럼, Monad는 unit과 flatMap을 가지고 있는 자료구조를 일반화한 특질이다.

Monad 만들기

arrow의 kind를 이용해서 Functor를 만들었던 것처럼 monad도 비슷한 방식으로 인터페이스를 정의해볼 수 있다.

interface Monad<F> {
    fun <A> unit(a: () -> A): Kind<F, A>
    fun <A, B> Kind<F, A>.flatMap(f: (A) -> Kind<F, B>): Kind<F, B>

한가지 흥미로운 점은, Functor에 등장하는 map 함수는 Monad의 unit과 flatMap을 이용해 아래와 같이 구현할 수 있다는 점이다.

map(f) == flatMap(a => unit(f(a)))

그러므로 Monad 인터페이스는 Functor 인터페이스를 상속하도록 하고, map 함수에 대해서는 default method를 제공해줄 수 있다.

interface Monad<F>: Functor<F> {
    fun <A> unit(a: () -> A): Kind<F, A>
    fun <A, B> Kind<F, A>.flatMap(f: (A) -> Kind<F, B>): Kind<F, B>
    override fun <A, B> Kind<F, A>.map(f: (A) -> B): Kind<F, B> = this.flatMap { unit { f(it) } }

그리고 Functor에서 했던 것과 같이 다양한 타입 생성자에 대해 Monad 인스턴스를 작성할 수 있다.

object ListMonad : Monad<ForListK> {
    override fun <A> unit(a: () -> A): Kind<ForListK, A> = ListK(listOf(a()))

    override fun <A, B> Kind<ForListK, A>.flatMap(f: (A) -> Kind<ForListK, B>): Kind<ForListK, B> = this.fix().flatMap { f(it).fix() }
}

object OptionMonad : Monad<ForOptionK> {
    override fun <A> unit(a: () -> A): Kind<ForOptionK, A> = OptionK(Optional.of(a()))

    override fun <A, B> Kind<ForOptionK, A>.flatMap(f: (A) -> Kind<ForOptionK, B>): Kind<ForOptionK, B> = OptionK(this.fix().option.flatMap { f(it).fix().option })
}

object IdMonad : Monad<ForIdK> {
    override fun <A> unit(a: () -> A): Kind<ForIdK, A> = IdK(a())

    override fun <A, B> Kind<ForIdK, A>.flatMap(f: (A) -> Kind<ForIdK, B>): Kind<ForIdK, B> = this.fix().flatMap { f(it).fix() }
}

PBT로 Monad 법칙 확인해보기

결합법칙

모든 Monad x는 임의의 함수 f, g에 대해 다음과 같은 결합법칙을 만족한다.

x.flatMap(f).flatMap(g) == x.flatMap(a => f(a).flatMap(g))

이 결합법칙을 확인하는 테스트 코드를 pbt 기반으로 아래와 같이 작성할 수 있다.

"monad associative law 1" {
        forAll<List<Int>> { seq ->
            monadAssociativeLaw(
                ListMonad,
                ListK(seq),
                { ListK(listOf(it, it + 1, it + 2)) }, // 임의의 lambda function
                { ListK(listOf(it, it * 10, it * 20)) } // 임의의 lambda function
            )
        }
    }

fun <F, A, B, C> monadAssociativeLaw(m: Monad<F>, monad: Kind<F, A>, f: (A) -> Kind<F, B>, g: (B) -> Kind<F, C>): Boolean =
    m.run {
        monad.flatMap(f).flatMap(g) == monad.flatMap { f(it).flatMap(g) }
    }

그런데 이 flatMap을 이용한 결합법칙의 표현은 다소 직관적이지 않을 수 있다. 다행히 아래의 compose 함수를 이용하면 결합법칙을 보다 명확하게 표현할 수 있다.

fun <A, B, C> compose(f: (A) -> Kind<F, B>, g: (B) -> Kind<F, C>): (A) -> Kind<F, C> = { f(it).flatMap(g) }

=> compose(compose(f, g), h) == compose(f, compose(g, h))

lambda function의 logical equality

이제 compose를 이용한 결합 법칙이 성립하는지 확인해 보아야 하는데, 한가지 고민해보아야 할 점은 compose 메소드의 리턴값은 하나의 lambda function이라는 점이다. 등식이 성립함을 확인하려면 좌항과 우항이 같은지를 비교해야 하는데, 이를 위해 lambda function의 logical equality를 어떻게 판단할 것언지에 대한 고민이 필요하다.

일단 lambda function은 logical equality를 판단할 수단이 없다. 자바와 코틀린은 클래스 기반의 객체 지향 언어이며 logical equality를 판단하기 위해서 equals 함수를 사용하는데, lambda function은 클래스가 아니기 때문에 equals를 override할 수 없다.

그래서 이 lambda function에 매개변수를 넣어줘서 나오는 결과값이 같은지를 비교해 보기로 결정했다. 결과적으로 compose를 이용한 결합법칙을 아래와 같이 보완하였다.

형식을 만족하는 모든 a에 대해
compose(compose(f, g), h)(a) == compose(f, compose(g, h))(a)

이제 이 법칙을 kotlin 코드로 정확하게 표현할 수 있고, 이를 이용해서 PBT 기반 테스트를 진행할 수 있다.

"monad associative law 2" {
        forAll<Int> { i ->
            monadAssociativeLaw2(
                ListMonad,
                i,
                { ListK(listOf(it, it + 1, it + 2)) }, // 임의의 lambda function
                { ListK(listOf(it, it * 10, it * 20)) }, // 임의의 lambda function
                { ListK(listOf(it, it - 3, it - 7)) } // 임의의 lambda function
            )
        }
    }

fun <F, A, B, C, D> monadAssociativeLaw2(m: Monad<F>, element: A, f: (A) -> Kind<F, B>, g: (B) -> Kind<F, C>, h: (C) -> Kind<F, D>): Boolean =
    m.run {
        compose(compose(f, g), h)(element) == compose(f, compose(g, h))(element)
    }

항등법칙

Monad에 대한 항등법칙은 왼쪽 항등 법칙과 오른쪽 항등 법칙이 각각 존재한다.
compose(f, unit) == f
compose(unit, f) == f

이 법칙들을 역시 flatMap으로도 표현해볼 수 있다.
x.flatMap(unit) == x
unit(y).flatMap(f) == f(y)

이번에도 compose를 이용한 표현에 대한 동등성 검사는 파라미터를 랜덤하게 넣어줌으로써 진행했다. (실제 테스트 코트는 귀찮아서 왼쪽 항등법칙만 작성했다 ...)

"monad identity law 1" {
        forAll<List<Int>> { seq ->
            monadIdentityLaw(ListMonad, ListK(seq))
        }
    }

"monad identity law 2" {
    forAll<Int> { i ->
        monadIdentityLaw2(ListMonad, i) {
            ListK(listOf(it.toString()))
        }
    }
}

fun <F, A> monadIdentityLaw(m: Monad<F>, monad: Kind<F, A>): Boolean =
    m.run {
        monad.flatMap { unit { it } } == monad
    }

fun <F, A, B> monadIdentityLaw2(m: Monad<F>, element: A, f: (A) -> Kind<F, B>): Boolean =
    m.run {
        compose(f, { unit { it } })(element) == f(element)
    }

법칙의 표현을 더 명확하게 하기 위해 compose를 만든 것인데, 실제 코틀린 코드로 표현하니 오히려 flatMap을 이용한 표현이 더 명확해 보이는건 기분탓일까? ㅎㅎ

짠