지난 시간 단테는 매핑함수의 일종인 폴드함수를 소개하며 컬렉션을 어떤 단일 값으로 줄여주는 폴드 함수를 통해 재귀를 순회할 때마다 컬렉션을 종료조건으로 수렴시키는 작업을 수행했었는데...

코틀린으로 배우는 함수형 프로그래밍을 읽으며 정리한 내용입니다.

복습삼아 폴드 함수에 대해 다시 짚고 넘어가자

컬렉션 데이터 단계별로 줄이기

자바스크립트에서 Array.prototype.reduce와 같이 iterable한 타입을 대상으로 순회하며 하나의 값으로 수렴하게 만드는 것을 접는다라고 하며 폴드한다라고 한다.

다음과 같이 리스트의 첫번째 부터 마지막까지 더해나가는 sum 함수가 있다고 할 때
sum 함수는 왼쪽에서 오른쪽으로 줄이기 때문에 fold left 하다고 한다. sum에는 하나의 값으로 수렴하는 로직과 더하는 로직 두가지가 혼잡해 있다. 수렴하게 하는 로직을 일반화 해보자.

fun sum(list: FunList<Int>): Int = when (list) {
    FunList.Nil -> 0
    is FunList.Cons -> list.head + sum(list.tail)
}

foldLeft 함수 만들기

tailrec fun <T,R> FunList<T>.foldLeft(acc: R, f: (R,T) -> R): R = when(this) {
  FunList.Nil -> acc
  is FunList.Cons -> tail.foldLeft(f(acc,head), f)
}

재귀 과정에서 this가 FunList.Nil에 매칭되면 원본 리스트의 모든 값을 순회했다는 것이므로 현재까지 작업된 acc을 반환하고, is FunList.Cons에 매칭되면 tail의 foldLeft 함수에 리스트의 가장 왼쪽에 있는 값 (head)를 빼서 f 함수의 매개변수로 사용한다.

위의 sum 함수는 다음과 같이 foldLeft, sumByFoldLeft의 결합으로 대체할 수 있다.

fun sumByFoldLeft(list: FunList<Int>): Int = list.foldLeft(0) { acc, x -> acc + x}

fun main() {
    val intList = Cons(1, Cons(2, Cons(3)))
    println(sumByFoldLeft(intList))
}

foldLeft 함수로 toUpper 함수 작성하기

toUpper 함수는 소문자의 리스트를 받아서 대문자의 리스트로 변경해준다.

fun toUpper(list: FunList<Char>): FunList<Char> = list.foldLeft(Nil) {
  acc: FunList<Char>, char: Char -> acc.appendTail(char.toUpperCase())
}

이제 확장함수로 만들자.

fun<T,R> FunList<T>.mapByFoldLeft(f: (T) -> R): FunList<R> = this.foldLeft(FunList.Nil) {
  acc: FunList<R>, x -> acc.appendTail(f(x))
}

foldRight 함수 만들기

fun <T, R> FunList<T>.foldRight(acc: R, f: (T,R) -> R): R = when (this) {
    FunList.Nil -> acc
    is FunList.Cons -> f(head, tail.foldRight(acc,f))
}

tailrec fun <T, R> FunList<T>.foldLeft(acc: R, f: (R, T) -> R): R = when(this) {
    FunList.Nil -> acc
    is FunList.Cons -> tail.foldLeft(f(acc,head), f)
}

foldRight는 오른쪽에서 왼쪽으로 줄여나가는 함수이다. 오른쪽에서 왼쪽으로 줄여나가기 때문에 head가 마지막에 연산되어야 한다.
foldLeft와 매우 유사하나 foldLeft와 다르게 꼬리 재귀가 아니다.

val intList = Cons(1, Cons(3, Cons(10)))
intList.foldRight(0) { x, acc -> x - acc }

f(1, [3,10].foldRight(0, { x, y -> x - y}), acc: 0 
f(1, f(3, [10].foldRight(0, { x, y -> x - y}), acc: 0
f(1, f(3, f(10, [].foldRight(0, { x, y -> x - y}))))
f(1, f(3, f(10,0)))
f(1, f(3,10))
f(1, -7)
8

foldLeft 함수는 스택에 안전하기 때문에 리스트의 크기가 커질 수 있고 f 함수의 실행 비용이 큰 경우 사용하는 것이 좋다.

그럼 foldRight 함수는 언제 사용해야 할까?

fun <T ,R> FunList<T>.mapByFoldLeft(f: (T) -> R): FunList<R> = foldLeft(FunList.Nil) {
    acc: FunList<R>, x -> acc.appendTail(f(x))
}
 
fun <T, R> FunList<T>.mapByFoldRight(f: (T) -> R): FunList<R> = foldRight(FunList.Nil) {
    x, acc: FunList<R> -> acc.addHead(f(x))
}

mapByFoldRight 함수를 살펴보면 foldRight는 addHead를 사용한다. appendTail은 O(2n)인 반면 addHead는 O(1)이기 때문에 실행 비용이 낮다.
따라서 일반적인 리스트의 경우 foldRight를 사용하는게 낫다.

명령형 방식과 함수형 방식의 성능 비교

fun imperativeWay(intList: List<Int>): Int {
    for (value in intList) {
        val doubleValue = value * value
        if( doubleValue < 10) {
            return doubleValue
        }
    }
    throw NoSuchElementException("there is no value")
}

fun functionalWay(intList: List<Int>): Int =
        intList
                .map {n -> n * n }
                .filter { n -> n < 10 }
                .first()

fun main() {
    val bigIntList = (1..10000000).toList()
    var start = System.currentTimeMillis()
    imperativeWay(bigIntList)
    println("${System.currentTimeMillis()}ms") // "0 ms"

    start = System.currentTimeMillis()
    functionalWay(bigIntList)
    println("${System.currentTimeMillis()}ms") // "2180 ms"
}

대단히 큰 리스트를 대상으로 동일한 연산을 실행할 때 함수형 방식이 더 오랜 시간이 걸리는 것을 알 수 있다.

이렇게 성능 차이가 나는 이유는 명령형 방식에서는 하나의 엘리먼트를 대상으로 map, filter의 로직을 같이 실행하는 반면, 함수형 방식에서는 map, filter등의 콤비네이터 연산마다 리스트를 전체 순회하기 때문이다.

코틀린의 컬렉션은 기본적으로 즉시평가를 하기 때문에 성능 비용이 크다.
언어마다 게으른 평가(lazy evaluation)을 제공하는 문법이 정해져있는데, 코틀린의 경우 시퀀스를 사용한다.

fun realFunctionalWay(intList: List<Int>): Int =
        intList.asSequence()
                .map { n -> n * n }
                .filter { n -> n < 10 }
                .first()

fun main() {
    val bigIntList = (1..10000000).toList()
    var start = System.currentTimeMillis()
    start = System.currentTimeMillis()
    realFunctionalWay(bigIntList)
    println("${System.currentTimeMillis()}ms") // “8 ms"
}

게으른 컬렉션 FunStream

앞서 만든 FunList는 생성자 매개변수를 적용하는 즉시 평가되는 반면에 FunStream은 일급 함수를 생성자 매개변수로 제공하기 때문에 꼭 필요한 순간에만 평가를 하는 게으른 평가 컬렉션이다.

sealed class FunList<out T> {
    object Nil: FunList<Nothing>()
    data class Cons<out T>(val head: T, val tail: FunList<T>):FunList<T>()
}

sealed class FunStream<out T> {
    object Nil: FunStream<Nothing>()
    data class Cons<out T>(val head: () -> T, val tail: () -> FunStream<T>) : FunStream<T>()
}

콤비네이터 스트림으로 재작성하기

appendTail 로직이다.

fun <T> FunStream<T>.appendTail(value: T): FunStream<T> = when (this) {
    FunStream.Nil -> FunStream.Cons({ value }, { FunStream.Nil })
    is FunStream.Cons -> FunStream.Cons(head, { tail().appendTail(value) })
}

filter와 map을 스트림 방식으로 재 구현했다.

tailrec fun <T> FunStream<T>.dropWhile(f: (T) -> Boolean): FunStream<T> = when (this) {
    FunStream.Nil -> this
    is FunStream.Cons -> if (f(head())) {
        this
    } else {
        tail().dropWhile(f)
    }
}

fun <T> FunStream<T>.filter(p: (T) -> Boolean): FunStream<T> = when (this) {
    FunStream.Nil -> FunStream.Nil
    is FunStream.Cons -> {
        val first = dropWhile(p)
        if (first != FunStream.Nil) {
            FunStream.Cons({ first.getHead() }, { first.getTail().filter(p) })
        } else {
            FunStream.Nil
        }
    }
}

fun <T, R> FunStream<T>.map(f: (T) -> R): FunStream<R> = when (this) {
    FunStream.Nil -> FunStream.Nil
    is FunStream.Cons -> FunStream.Cons({ f(head()) }, { tail().map(f) })
}

다시 성능비교 해보자

fun funListWay(intList: FunList<Int>): Int = intList
        .map { n -> n * n }
        .filter { n -> n < 1000000 }
        .map { n -> n - 2 }
        .filter { n -> n < 1000 }
        .map { n -> n * 10 }
        .getHead()

fun funStreamWay(intList: FunStream<Int>): Int = intList
        .map { n -> n * n }
        .filter { n -> n < 1000000 }
        .map { n -> n - 2 }
        .filter { n -> n < 1000 }
        .map { n -> n * 10 }
        .getHead()

fun main() {
    val bigIntList = (1..10000000).toFunList()
    var start = System.currentTimeMillis()
    funListWay(bigIntList)
    println("${System.currentTimeMillis() - start} ms")    // 9467 ms

    val bigIntStream = (1..10000000).toFunStream()
    start = System.currentTimeMillis()
    funStreamWay(bigIntStream)
    println("${System.currentTimeMillis() - start} ms")    // 7 ms
}

기존 FunList보다 성능이 월등하게 나아졌음을 알 수 있다.

무한대 값 저장하기

일반적인 데이터 구조로는 무한대 값을 저장할 수 없다. 값을 저장하기 위해서는 평가해야 하는데, 평가를 한다는 것은 메모리 위에 올리는 것이고 무한대 값은 메모리 위에 올릴 수 없기 때문이다.

따라서 무한대 값을 저장하기 위해서는 스트림과 같이 무한대 값을 표현하는 함수를 저장해야 한다.
값 그 자체를 저장하는 것이 아니라 값을 표현하는 함수를 저장하는 것이다.

다음의 generateFunStream 함수는 seed 값에서 시작해 그 다음 Cons에 그 다음번 증가 값을 반환하는 함수를 head에 넣는다. 이렇게 하면 평가가 필요한 순간에만 선택적으로 메모리 위에 올릴 수 있다.

fun <T> generateFunStream(seed: T, generate: (T) -> T): FunStream<T> =
        FunStream.Cons({ seed }, { generateFunStream(generate(seed), generate) })

forEach의 람다 표현식으로 println을 넣었다. 메모리에서 표현하기 힘들만큼 큰 숫자가 메모리 위에 올라가거나 사용자가 임의로 프로그램을 멈추지 않는 이상 계속 돌아갈 것이다.

fun main() {
    val infiniteVal = generateFunStream(0) { it + 5 }
    infiniteVal.forEach { println (it)}
}

tailrec fun <T> FunStream<T>.forEach(f: (T) -> Unit): Unit = when (this) {
    FunStream.Nil -> Unit
    is FunStream.Cons -> {
        f(head())
        tail().forEach(f)
    }
}