<div id="readability-page-1" class="page"><div><a href="https://github.com/BaekGeunYoung/kotest_pbt_practice/blob/master/src/test/kotlin/com/example/demo/MonoidTest.kt">깃헙 코드 바로가기</a>
<h2 id="모노이드">모노이드</h2>
하나의 모노이드는 다음과 같은 요소들로 구성된다.
<ul>
<li>어떤 형식 A</li>
<li>A 형식의 값 2개를 받아서 하나의 값을 산출하는 결합적 이항 연산 op.</li>
<li>이 연산 op에 대한 한등원 zero.</li>
</ul>
그리고 op는 아래와 같은 결합 법칙을 만족해야 한다.
<pre><code>op(op(x, y), z) == op(x, op(y, z))</code></pre>
그리고 항등원 zero는 아래 법칙을 만족한다.
<pre><code>op(x, zero) == op(zero, x) == x</code></pre>
<h2 id="모노이드-만들기">모노이드 만들기</h2>
위에서 설명한 모노이드의 개념을 코드로 구체화시켜보면 아래와 같은 인터페이스로 표현할 수 있다.
<pre><code>interface Monoid &lt;A&gt; {
 val zero: A
 fun op(a1: A, a2: A): A
}</code></pre>
그리고 이 인터페이스를 상속하는 다양한 모노이드를 만들 수 있다.
<pre><code>val intAddition = object: Monoid&lt;Int&gt; {
 override val zero: Int = 0
 override fun op(a1: Int, a2: Int): Int = a1 + a2
}

val intMultiplication = object : Monoid&lt;Int&gt; {
 override val zero: Int = 1
 override fun op(a1: Int, a2: Int): Int = a1 * a2
}

val booleanOr = object : Monoid&lt;Boolean&gt; {
 override val zero: Boolean = false
 override fun op(a1: Boolean, a2: Boolean): Boolean = a1 || a2
}

val booleanAnd = object : Monoid&lt;Boolean&gt; {
 override val zero: Boolean = true
 override fun op(a1: Boolean, a2: Boolean): Boolean = a1 &amp;&amp; a2
}</code></pre>
<h2 id="pbt로-모노이드-법칙-확인하기">PBT로 모노이드 법칙 확인하기</h2>
항등법칙과 결합법칙은 각각 아래와 같은 코드로 표현될 수 있다.
<pre><code>fun &lt;A&gt; monoidIdentityLaw(m: Monoid&lt;A&gt;, element: A): Boolean =
 m.op(element, m.zero) == element &amp;&amp; m.op(m.zero, element) == element

fun &lt;A&gt; monoidAssociativeLaw(m: Monoid&lt;A&gt;, elements: Triple&lt;A, A, A&gt;): Boolean =
 m.op(m.op(elements.first, elements.second), elements.third) == m.op(elements.first, m.op(elements.second, elements.third))</code></pre>
그리고 이를 PBT 기반으로 테스팅하는 함수로 한번 더 감싸주었다.
<pre><code>suspend inline fun &lt;reified A&gt; Monoid&lt;A&gt;.monoidIdentityLawProp(): PropertyContext =
 forAll&lt;A&gt; { a -&gt;
 monoidIdentityLaw(this@monoidIdentityLawProp, a)
 }

suspend inline fun &lt;reified A&gt; Monoid&lt;A&gt;.monoidAssociativeLawProp(): PropertyContext =
 forAll&lt;A, A, A&gt; { a, b, c -&gt;
 monoidAssociativeLaw(this@monoidAssociativeLawProp, Triple(a, b, c))
 }</code></pre>
이를 사용하는 실제 테스트 코드는 아래와 같다.
<pre><code>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()
 }
}</code></pre>
<h2 id="모노이드-준동형사상homomorphism">모노이드 준동형사상(homomorphism)</h2>
모노이드 M과 N 사이의 모노이드 준동형사상 f는 모든 x, y 값에 대해 다음과 같은 일반 법칙을 따른다: 
<code>M.op(f(x), f(y)) == f(N.op(x, y))</code>
모노이드 준동형사상의 한 예시로, <code>List&lt;Char&gt;</code>를 <code>String</code>으로 결합하는 연산을 꼽을 수 있다.
<pre><code>val f : (List&lt;Char&gt;) -&gt; String = {
 it.foldRight("") { a, b -&gt;
 a + b
 }
}</code></pre>
이 f는 모노이드 준동형사상이므로, 아래와 같은 식을 만족해야 한다.
<pre><code>f(charsConcatMonoid.op(x, y)) == strConcatMonoid.op(f(x), f(y))</code></pre>
이를 kotest를 이용해 아래와 같이 작성할 수 있다.
<pre><code>val f : (List&lt;Char&gt;) -&gt; String = {
 it.foldRight("") { a, b -&gt;
 a + b
 }
 }

forAll&lt;List&lt;Char&gt;, List&lt;Char&gt;&gt; { x, y -&gt;
 f(charsConcatMonoid.op(x, y)) == stringConcatMonoid.op(f(x), f(y))
}</code></pre>
<h2 id="모노이드-동형사상isomorphism">모노이드 동형사상(isomorphism)</h2>
위의 함수 f에 대한 한 가지 흥미로운 사실은, f의 역연산인 String을 Char의 List로 분해하는 사상 또한 모노이드 준동형사상이라는 것이다.
<pre><code>val g : (String) -&gt; List&lt;Char&gt; = {
 it.toCharArray().toList()
}

forAll&lt;String, String&gt; { x, y -&gt;
 g(stringConcatMonoid.op(x, y)) == charsConcatMonoid.op(g(x), g(y))
}</code></pre>
이렇게 두 모노이드 사이에 준동형사상이 양방향으로 존재할 때, 짝을 이루는 두 개의 준동형사상을 함께 동형사상이라고 말하며, 이 때의 두 모노이드를 동형(isomorphic)이라고 칭한다. 이 때 f와 g는 서로 역연산 관계에 있으며, <code>f(g(x)) == g(f(x)) == x</code> 이다.</div></div>

백근영.log

깃헙 코드 바로가기
모노이드
하나의 모노이드는 다음과 같은 요소들로 구성된다.
어떤 형식 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 이다.

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

댓글