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

Functor

우리는 함수형 프로그래밍 패러다임을 지원하는 많은 언어에서 다양한 자료 구조에 대해 map 함수를 지원하는 것을 알고 있다. 이러한 이른바 "map 함수를 구현하는 자료 구조"를 일반화한 특질을 Functor라고 부른다.

Functor 만들기

functor는 어떤 형식(type)에 대한 것이 아니라 형식 생성자(type constructor)에 대한 것인데, 코틀린에서는 이 형식 생성자를 generic하게 표현하는 방법을 지원하지 않는다. 대표적인 함수형 언어인 스칼라에서는 상위 형식 생성자(higher kinded type)라고 불리는 개념을 기본 syntax로 제공하는데, 코틀린에서 이 higher kinded type을 표현하기 위해서는 코틀린 함수형 라이브러리인 arrow의 힘을 빌려야 한다.

higher kinded type을 표현하기 위해 arrow에서 제공하는 Kind 형식을 사용해 Functor 인터페이스를 아래와 같이 작성할 수 있다.

import arrow.Kind

interface Functor <F> {
    fun <A, B> Kind<F, A>.map(f: (A) -> B): Kind<F, B>
}

그리고 이 인터페이스를 상속하는 다양한 Functor 인스턴스를 생성하면 되는데, 그렇게 하기 위해서는 몇 가지 sugar syntax가 필요하다.

예를 들어 List라는 형식 생성자에 대한 Functor 인스턴스를 만들고 싶을 때, Functor <F>에서 F 자리에 들어갈 형식을 하나 정의해야 한다. 이 형식은 아무 내용을 담고 있지 않은 껍데기이며, 이름은 List를 위한 상위 형식 생성자라는 점에서 ForList 정도로 한다.

class ForList private constructor()

이제 우리는 Kind<ForList, A>라는 형식을 가지고 map 함수를 구현해야 하는데, 이 Kind<ForList, A>와 실제 데이터를 담고 있는 List를 연결시켜줄 또 하나의 클래스가 필요하다. 이 클래스는 List의 실제 데이터를 담고 있어야 하며, Kind<ForList, A>의 하위 타입이어야 할 것이다.

@higherkind
data class ListK<T>(val list: List<T>) : Kind<ForListK, T>, List<T> by list

그리고 이렇게 만들어진 ListK<T>와 Kind<ForListK, T> 간의 type casting을 해주는 편의함수도 추가해주면 좋을 것이다.

@Suppress("UNCHECKED_CAST")
fun <A> Kind<ForListK, A>.fix(): ListK<A> = this as ListK<A>

이제 모든 준비가 끝났고, 아래와 같은 ListFunctor 인스턴스를 만들 수 있다.

object ListFunctor : Functor<ForListK> {
    override fun <A, B> Kind<ForListK, A>.map(f: (A) -> B): Kind<ForListK, B> = fix().map(f)
}

같은 방법으로 Option과 Id 형식에 대해서도 Functor 인스턴스를 만들 수 있다.

object OptionFunctor : Functor<ForOption> {
    override fun <A, B> Kind<ForOption, A>.map(f: (A) -> B): Kind<ForOption, B> = fix().map(f)
}

object IdFunctor : Functor<ForId> {
    override fun <A, B> Kind<ForId, A>.map(f: (A) -> B): Kind<ForId, B> = fix().map(f)
}

PBT로 Functor 법칙 확인해보기

Functor는 map 함수에 대해 아래와 같은 항등 법칙을 만족한다.

(어떤 Functor x를 항등 함수로 사상한 결과는 자기 자신과 같다.)
x.map(a => a) == x

이 항등 법칙을 확인하기 위한 함수를 코틀린으로 표현하면 아래와 같다.

fun <F, A> functorIdentityLaw(f: Functor<F>, functor: Kind<F, A>): Boolean =
    f.run {
        functor.map { it } == functor
    }

그리고 이 함수를 이용해, 아래와 같이 다양한 Functor 인스턴스와 이 Functor에 들어갈 랜덤 값들로 테스트를 해볼 수 있다.

class FunctorTest : StringSpec({
    "functor identity law - int list" {
        forAll<List<Int>> { seq ->
            functorIdentityLaw(ListFunctor, ListK(seq))
        }
    }

    "functor identity law - string list" {
        forAll<List<String>> { seq ->
            functorIdentityLaw(ListFunctor, ListK(seq))
        }
    }

    "functor identity law - int option" {
        forAll<Int> { i ->
            functorIdentityLaw(OptionFunctor, OptionK(Optional.of(i)))
        }
    }
    "functor identity law - string option" {
        forAll<Int> { i ->
            functorIdentityLaw(OptionFunctor, OptionK(Optional.of(i)))
        }
    }
    "functor identity law - int id" {
        forAll<String> { i ->
            functorIdentityLaw(IdFunctor, IdK(i))
        }
    }
    "functor identity law - string id" {
        forAll<String> { i ->
            functorIdentityLaw(IdFunctor, IdK(i))
        }
    }
})

테스트 성공 !