6. 순수 함수형 상태

Random 함수를 생각해보자.

import kotlin.random.Random

fun main() {
    val rng = Random
    rng.nextInt()
}

rng.nextInt()를 할 때마다 다른 값이 나온다. 
왜일까? rng는 그대로인데..

Random 안에서 어떤 "상태"를 변경하기 때문이다. 

다들 알다시피 함수형 프로그램에서 이런 가변 상태는 부수효과이고, 참조투명하지 않다. 

또한 테스트 하기도 어려워진다. 

fun rollDice(): Int {
    val rng = Random
    return rng.nextInt(6)
}

이런 주사위를 던지는 함수를 생각해보자. nextInt(6)을 했지만, 실제로는 0~5까지의 범위가 나온다. 
잘못 작성한 함수라는 것이다. 

1~5 범위의 수가 나오면 사용자는 오류인지 모를것이다. 따라서 1/6의 확률로 오류가 발생하는 것이다. 
일반적으로는 이런 함수보다 오류 상황을 더 예측하기 힘들다. 그리고 오류가 발생했을 때 안정적으로 재생산을 할 수 있어야 한다. 

이번 장에서는 함수형 프로그래밍에서 이런 상태 전이를 처리하는 법을 알아본다.

명령형 해법이 아닌 순수 함수형 방식으로 말이다!

순수 함수형 난수 생성기

부수효과를 제거하고, 참조투명성을 회복시켜보자.

이제부터는 "상태 갱신"을 명시화 할 것이다. 위에서 본 kotlin의 Random처럼 내부의 상태가 아무도 모르게 변하는 것이 아니라 사용자가 알 수 있게 하겠다는 뜻이다.

interface RNG {
    fun nextInt(): Pair<Int, RNG>
}

이 인터페이스를 보자. 반환을 Pair로한다. Int는 랜덤 생성된 난수이고, RNG는 다음 상태를 말한다.
즉, 난수를 생성하면 난수 값과 새 상태를 함께 돌려주는 것이다. 

이 인터페이스를 구현해보자. linear congruential generator라는 알고리듬을 사용할 것이다.

data class SimpleRNG(val seed: Long) : RNG {
    override fun nextInt(): Pair<Int, RNG> {
        val newSeed = (seed * 0x5DEECE66DL + 0xBL) and 0xFFFFFFFFFFFFL
        val nextRNG = SimpleRNG(newSeed)
        
        val n = (newSeed ushr 16).toInt()
        return n to nextRNG
    }
}

• 이 명령은 원하는 만큼 반복해서 실행할 수 있다.
• 같은 시드 값에 대해서는 항상 같은 값을 얻는다.
• 결과로 나온 RNG에 대해서도 같은 난수를 얻는다.

상태가 있는 API를 순수 함수형 API로 만들기

위에서는 난수 생성기를 순수 함수형 API로 만들어 봤다.

이렇게 API가 내부의 무언가를 변이 시키는 대신 다음 상태를 계산하게 만드는 문제는 다른 문제에도 사용할 수 있다. 

class MutatingSequencer {
    private var repo: Repository = TODO()
    fun nextInt(): Int = TODO()
    fun nextDouble(): Double = TODO()
}

어떤 수 시퀀스를 만드는 Repository가 있다고 하자.
nextInt()와 nextDouble()은 repo를 통해 값을 받아와 출력할 것이다. 그리고 각각의 방식으로 repo의 상태를 변경할 것이다.(인덱스에 +1을 한다거나 등)

이런 부수효과가 있는 함수를 순수 함수형으로 만드려면? 
위에서도 말했죠! 상태 갱신을 명시화

interface StateActionSequencer {
    fun nextInt(): Pair<Int, StateActionSequencer>
    fun nextDouble(): Pair<Double, StateActionSequencer>
}

현재 값과, 다음 상태를 반환합니다. 이러믄 다음 상태를 전달할 책임을 호출자 쪽에서 져야합니다.

연습문제 6.1

fun nonNegativeInt(rng: RNG): Pair<Int, RNG> {
    val cur = rng.nextInt()
    return if (cur.first < 0) {
        if (cur.first == Int.MIN_VALUE) {
            Int.MAX_VALUE to cur.second
        } else {
            abs(cur.first) to cur.second
        }
    } else {
        cur
    }
}

fun nonNegativeInt2(rng: RNG): Pair<Int, RNG> {
    val (value, next) = rng.nextInt()
    return (if (value < 0) -(value + 1) else value) to next
}

연습문제 6.2

fun double(rng: RNG): Pair<Double, RNG> {
    val (value, next) = nonNegativeInt(rng)
    return (value / (Int.MAX_VALUE.toDouble() + 1)) to next
}

연습문제 6.3

fun intDouble(rng: RNG): Pair<Pair<Int, Double>, RNG> {
    val (i, rng1) = rng.nextInt()
    val (d, rng2) = double(rng1)
    return (i to d) to rng2
}

fun doubleInt(rng: RNG): Pair<Pair<Double, Int>, RNG> {
    val (d, rng1) = double(rng)
    val (i, rng2) = rng1.nextInt()
    return (d to i) to rng2
}

fun double3(rng: RNG): Pair<Triple<Double, Double, Double>, RNG> {
    val (d, rng1) = double(rng)
    val (d1, rng2) = double(rng1)
    val (d2, rng3) = double(rng2)
    return Triple(d, d1, d2) to rng3
}

연습문제 6.4

fun ints(count: Int, rng: RNG): Pair<List<Int>, RNG> {
    if (count == 0) return Nil to rng
    val (i, rng1) = rng.nextInt()
    val (list, rng2) = ints(count - 1, rng1)
    return Cons(i, list) to rng2
}

상태 동작을 전달하는 암시적 접근 방법

앞에서의 순수 함수형 해법은 뭐였지. "상태 갱신 명시화" 였다.

이 해법은 부수효과를 피할 수 있지만, 순차적이며, 오류를 저지르기 쉽고, 번거롭다.

지금까지 공통되는 패턴은  (RNG) -> Pair<A, RNG> 이었다. 모든 함수가 이 패턴을 따라 만들어졌다.

처음의 RNG 상태에서 다른 RNG 상태를 반환한다. 이를 상태 전이/동작이라고 한다.

상태 전이/동작은 콤비네이터를 통해 조합할 수 있다. 직접 상태를 반복적으로 처리하지 않고 콤비네이터가 자동으로 다음 동작을 하게 만들어보자.

typealias Rand<A> = (RNG) -> Pair<A, RNG>

// 함수를 반환
val intR: Rand<Int> = { rng -> rng.nextInt() }

Rand<A>라는 타입을 만들었다. 이는 함수 타입이다. 

intR은 함수를 반환하고, intR(SimpleRNG(10)) 이런 식으로 사용할 수 있다.

fun <A> unit(a: A): Rand<A> = { rng -> a to rng }

fun <A, B> map(s: Rand<A>, f: (A) -> B): Rand<B> = { rng ->
    val (a, rng2) = s(rng)
    f(a) to rng2
}

이렇게 상태를 사용하지 않고 파라미터로 받은 상수를 반환하는 unit함수와 상태를 변경하지 않으면서 출력을 변환하는 map도 있다. 

연습문제 6.5

fun doubleR(): Rand<Double> =
    map(::nonNegativeInt) { value ->
        value / (Int.MAX_VALUE.toDouble() + 1)
    }

상태 동작 조합을 통해 더 큰 능력 발휘하기

상태 전이를 감추고 단일 상태 동작을 다루는 API를 개발하였다. 

하지만 map은 intDouble, doubleInt 같은 함수를 구현할 수 없다. 단항 함수가 아니라 이항 함수를 사용해 두 가지 RNG 동작을 조합할 수 있는 map2를 만들자.

연습문제 6.6

fun <ITEM1, ITEM2, RESULT> map2(
    ra: Rand<ITEM1>,
    rb: Rand<ITEM2>,
    f: (ITEM1, ITEM2) -> RESULT
): Rand<RESULT> = { rng ->
    val (item1, rng1) = ra(rng)
    val (item2, rng2) = rb(rng1)
    
    f(item1, item2) to rng2
}

map2를 활용해 both 함수를 만들 수 있다.

fun <ITEM1, ITEM2> both(ra: Rand<ITEM1>, rb: Rand<ITEM2>): Rand<Pair<ITEM1, ITEM2>> =
    map2(ra, rb) { a, b -> a to b }

val intDoubleR: Rand<Pair<Int, Double>> = both(intR, doubleR)
val doubleIntR: Rand<Pair<Double, Int>> = both(doubleR, intR)

both를 사용해 intDouble, doubleInt를 만들 수 있다.

연습문제 6.7

fun <ITEM> sequence(fs: List<Rand<ITEM>>): Rand<List<ITEM>> = { rng ->
    when (fs) {
        is Nil -> Nil to rng
        is Cons -> {
            val (item, rng1) = fs.head(rng)
            val (list, rng2) = sequence(fs.tail)(rng1)
            Cons(item, list) to rng2
        }
    }
}

fun <ITEM> sequenceFold(fs: List<Rand<ITEM>>): Rand<List<ITEM>> = { rng ->
    foldRight(fs, Nil to rng) { head: Rand<ITEM>, tail: Pair<List<ITEM>, RNG> ->
        val (item, rng1) = head(rng)
        val (list, _) = tail
        Cons(item, list) to rng1
    }
}

fun <ITEM> sequenceFold2(fs: List<Rand<ITEM>>): Rand<List<ITEM>> =
    foldRight(fs, unit(Nil)) { item: Rand<ITEM>, acc: Rand<List<ITEM>> ->
        map2(item, acc) { h, t ->
            Cons(h, t)
        }
    }

상태 동작을 내포시켜서 재귀적으로 재시도하기

우리는 위에서 부터 랜덤 수를 생성하는 예제를 개선해왔다. 

1. kotlin.math.Random 객체의 내부 상태를 변이

2. 상태 동작을 명시적으로 전달하는 방식 ((RNG) -> Pair<ITEM, RNG>)

3. 상태 전이를 뒤에 감추는 방식 (Rand<ITEM>)

이런 단계를 거쳤다.

그리고 map, map2 콤비네이터를 이용해서 문제를 쉽게 해결할 수 있었다.
하지만 map, map2로도 쉽게 작성할 수 없는 함수도 있다.

0이상 n 미만의 정수를 랜덤 생성해주는 nonNegativeLessThan 함수를 작성해보자.

fun nonNegativeLessThan(n: Int): Rand<Int> =
	map(::nonNegativeInt) { it % n }

이렇게 작성할 수 있겠다. 이 함수는 우리가 원하는 범위의 값을 생성하지만, 나오는 수의 분포가 치우쳐져 있다.
Int.MAX_VALUE가 n의 배수여야 고른 분포가 나온다

무슨말이냐면? 예를 들어 Int.MAX_VALUE가 8이라고 해보자. 가정이다.
nonNegativeLessThan을 하면 -> 12340123 이런 분포이다. 1,2,3 은 나올 확율이 1/4이지만, 4, 0은 1/8인 것을 볼 수 있다.
8 % 5 = 3, 즉 Int.MAX_VALUE % n보다 작은 수는 좀 더 자주 발생한다.

그러니, 랜덤으로 뽑은 수가 n의 배수 중 최대값을 넘는다면 (6, 7, 8 이 나온다면) 더 작은 수를 얻기 위해 재시도 해야한다. 

fun nonNegativeLessThan(n: Int): Rand<Int> =
    map(::nonNegativeInt) { i ->
        val mod = i%n
        if (i + (n - 1) - mod >= 0) mod
        else nonNegativeLessThan(n) { i2 -> ?? }
    }

재귀를 써야하지만, Rand<Int>를 반환해야하는데, map을 사용해서는 할 수가 없다.

fun nonNegativeLessThan(n: Int): Rand<Int> = { rng ->
    val (i, rng2) = nonNegativeInt(rng)
    val mod = i % n
    if (i + (n - 1) - mod >= 0) {
        mod to rng
    } else {
        nonNegativeLessThan(n)(rng2)
    }
}

map을 사용해서 상태 이전을 감추는 대신 명시적으로 RNG를 반환받아 전달할 수 있다. 
하지만 우리는 여전히 상태 이전을 감추고 싶다. 새로운 콤비네이터 flatMap을 만들어보자.

연습문제 6.8

fun <ITEM, RESULT> flatMap(f: Rand<ITEM>, g: (ITEM) -> Rand<RESULT>): Rand<RESULT> = { rng ->
    val (item, rng1) = f(rng)
    g(item)(rng1)
}

fun nonNegativeLessThan2(n: Int): Rand<Int> =
    flatMap(::nonNegativeInt) { item: Int ->
        val mod = item % n
        
        if (item + (n - 1) - mod >= 0) {
            unit(mod)
        } else {
            nonNegativeLessThan2(n)
        }
    }

연습문제 6.9

fun <ITEM, RESULT> mapF(s: Rand<ITEM>, f: (ITEM) -> (RESULT)): Rand<RESULT> =
    flatMap(s) { item ->
        unit(f(item))
    }

fun <ITEM1, ITEM2, RESULT> map2F(ra: Rand<ITEM1>, rb: Rand<ITEM2>, f: (ITEM1, ITEM2) -> RESULT): Rand<RESULT> =
    flatMap(ra) { item1 ->
        mapF(rb) { item2 ->
            f(item1, item2)
        }
    }

일반적인 상태 동작 타입

지금까지 난수 생성에 대한 코드만 주구장창 봤다. 이거 어떻게 다른 문제에 적용할 수 있을까?

임의의 상태 동작에 대해 적용할 수 있는 타입과 함수로 만들어보자.

data class State<STATE, out ITEM>(val run: (STATE) -> Pair<ITEM, STATE>)

typealias Rand2<ITEM> = State<RNG, ITEM>

연습문제 6.10

fun <STATE, ITEM> unitS(item: ITEM): State<STATE, ITEM> = State { state ->
    item to state
}

fun <STATE, ITEM, RESULT> flatMapS(f: State<STATE, ITEM>, g: (ITEM) -> State<STATE, RESULT>): State<STATE, RESULT> =
   State { state -> 
       val (item, state1) = f.run(state)
       g(item).run((state1))
   }

fun <STATE, ITEM, RESULT> mapS(s: State<STATE, ITEM>, f: (ITEM) -> RESULT): State<STATE, RESULT> = 
    flatMapS(s) { item ->
        unitS(f(item))
    }

fun <STATE, ITEM1, ITEM2, RESULT> map2S(s1: State<STATE, ITEM1>, s2: State<STATE, ITEM2>, f: (ITEM1, ITEM2) -> RESULT): State<STATE, RESULT> =
    flatMapS(s1) { item1 ->
        mapS(s2) { item2 ->
            f(item1, item2)
        }
    }

fun <STATE, ITEM> sequenceS(fs: List<State<STATE, ITEM>>): State<STATE, List<ITEM>> = 
    foldRight(fs, unitS<STATE, List<ITEM>>(Nil)) { item, acc ->
        map2S(item, acc) { h, t ->
            Cons(h, t)
        }
    }