PBT로 FP 법칙 확인해보기 - 모노이드

깃헙 코드 바로가기

모노이드

하나의 모노이드는 다음과 같은 요소들로 구성된다.

• 어떤 형식 A
• A 형식의 값 2개를 받아서 하나의 값을 산출하는 결합적 이항 연산 op.
• 이 연산 op에 대한 한등원 zero.

그리고 op는 아래와 같은 결합 법칙을 만족해야 한다.

op(op(x, y), z) == op(x, op(y, z))

그리고 항등원 zero는 아래 법칙을 만족한다.

op(x, zero) == op(zero, x) == x

모노이드 만들기

위에서 설명한 모노이드의 개념을 코드로 구체화시켜보면 아래와 같은 인터페이스로 표현할 수 있다.

interface Monoid <A> {
    val zero: A
    fun op(a1: A, a2: A): A
}

그리고 이 인터페이스를 상속하는 다양한 모노이드를 만들 수 있다.

val intAddition = object: Monoid<Int> {
    override val zero: Int = 0
    override fun op(a1: Int, a2: Int): Int = a1 + a2
}

val intMultiplication = object : Monoid<Int> {
    override val zero: Int = 1
    override fun op(a1: Int, a2: Int): Int = a1 * a2
}

val booleanOr = object : Monoid<Boolean> {
    override val zero: Boolean = false
    override fun op(a1: Boolean, a2: Boolean): Boolean = a1 || a2
}

val booleanAnd = object : Monoid<Boolean> {
    override val zero: Boolean = true
    override fun op(a1: Boolean, a2: Boolean): Boolean = a1 && a2
}

PBT로 모노이드 법칙 확인하기

항등법칙과 결합법칙은 각각 아래와 같은 코드로 표현될 수 있다.

fun <A> monoidIdentityLaw(m: Monoid<A>, element: A): Boolean =
    m.op(element, m.zero) == element && m.op(m.zero, element) == element

fun <A> monoidAssociativeLaw(m: Monoid<A>, elements: Triple<A, A, A>): Boolean =
    m.op(m.op(elements.first, elements.second), elements.third) == m.op(elements.first, m.op(elements.second, elements.third))

그리고 이를 PBT 기반으로 테스팅하는 함수로 한번 더 감싸주었다.

suspend inline fun <reified A> Monoid<A>.monoidIdentityLawProp(): PropertyContext =
    forAll<A> { a ->
        monoidIdentityLaw(this@monoidIdentityLawProp, a)
    }

suspend inline fun <reified A> Monoid<A>.monoidAssociativeLawProp(): PropertyContext =
    forAll<A, A, A> { a, b, c ->
        monoidAssociativeLaw(this@monoidAssociativeLawProp, Triple(a, b, c))
    }

이를 사용하는 실제 테스트 코드는 아래와 같다.

class MonoidTest : StringSpec({
    "monoid identity law" {
        intAddition.monoidIdentityLawProp()

        intMultiplication.monoidIdentityLawProp()

        booleanAnd.monoidIdentityLawProp()

        booleanOr.monoidIdentityLawProp()
    }

    "monoid associative law" {
        intAddition.monoidAssociativeLawProp()

        intMultiplication.monoidAssociativeLawProp()

        booleanAnd.monoidAssociativeLawProp()

        booleanOr.monoidAssociativeLawProp()
    }
}

모노이드 준동형사상(homomorphism)

모노이드 M과 N 사이의 모노이드 준동형사상 f는 모든 x, y 값에 대해 다음과 같은 일반 법칙을 따른다:
M.op(f(x), f(y)) == f(N.op(x, y))

모노이드 준동형사상의 한 예시로, List<Char>를 String으로 결합하는 연산을 꼽을 수 있다.

val f : (List<Char>) -> String = {
    it.foldRight("") { a, b ->
        a + b
    }
}

이 f는 모노이드 준동형사상이므로, 아래와 같은 식을 만족해야 한다.

f(charsConcatMonoid.op(x, y)) == strConcatMonoid.op(f(x), f(y))

이를 kotest를 이용해 아래와 같이 작성할 수 있다.

val f : (List<Char>) -> String = {
        it.foldRight("") { a, b ->
            a + b
        }
    }

forAll<List<Char>, List<Char>> { x, y ->
    f(charsConcatMonoid.op(x, y)) == stringConcatMonoid.op(f(x), f(y))
}

모노이드 동형사상(isomorphism)

위의 함수 f에 대한 한 가지 흥미로운 사실은, f의 역연산인 String을 Char의 List로 분해하는 사상 또한 모노이드 준동형사상이라는 것이다.

val g : (String) -> List<Char> = {
    it.toCharArray().toList()
}

forAll<String, String> { x, y ->
    g(stringConcatMonoid.op(x, y)) == charsConcatMonoid.op(g(x), g(y))
}

이렇게 두 모노이드 사이에 준동형사상이 양방향으로 존재할 때, 짝을 이루는 두 개의 준동형사상을 함께 동형사상이라고 말하며, 이 때의 두 모노이드를 동형(isomorphic)이라고 칭한다. 이 때 f와 g는 서로 역연산 관계에 있으며, f(g(x)) == g(f(x)) == x 이다.