前回の授業でダンテはマッピング関数のボルド関数を紹介し、集合を単一値のボルド関数に縮小することで、再帰するたびに集合を終了条件に収束する操作を実行しました.코틀린으로 배우는 함수형 프로그래밍을 읽으며 정리한 내용입니다.復習として、ボルド関数を再検討しましょう.

データの収集を段階的に削減

JavaScriptでArrayprototype.reduceのように、測定可能なタイプを巡回し、접는다、폴드と呼ばれる値に収束させる.
リストに最初から最後に加算されたsum関数がある場合は、次のようにします.
sum関数はfoldleftと呼ばれます.左から右に減少しているからです.sumには2つの論理が混合されている:1つの値に収束する論理と加算された論理.収束させる論理を一般化しましょう.

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)
}

回帰中はFunListNilに一致すると、これまでに作成されたaccが返され、元のリストのすべての値、すなわち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(2 n)であり、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"
}

非常に大きなリストに対して同じ演算を実行すると,関数化方式にはより長い時間がかかることがわかる.
このようなパフォーマンスの違いは、コマンド型方式では1つのユニットに対してmap、filterの論理が同時に実行され、関数型方式ではmap、filterなどの組合せ演算子ごとにリストが全循環するためである.
コトリンの集合は基本的に即時評価されるため,性能コストが高い.
各言語は、Cottinに対してシーケンスを使用する怠惰評価(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はコンストラクション関数パラメータとして1次関数を提供するため、必要に応じて評価される怠惰な評価集合である.

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) })
}

フィルタと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で2番目に増分値を返す関数をheadに入れます.これにより、評価が必要な場合にのみ、メモリに選択的に配置できます.

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

forEachのRamda式で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)
    }
}