Wie erreicht man eine reine Funktion mit dynamischer Programmierung in Kotlin?

Question

Ich habe versucht, einige meiner Code zu reinen Funktionen zu transformieren, um zu lernen, wie Kotlin in einer funktionalen Weise zu verwenden, mit diesem einfachen Code-Schnipsel kann ich mir keinen Weg vorstellen, meine calculateFibonacci Funktion eine reine Funktion zu machen.

Ich bin mir einer potenziell rekursiven Lösung bewusst, aber was ist mit einem potenziellen Stack-Überlauf, implementiert Kotlin Tail Call Optimization?

Beispiel:

 val fibonacciValues = hashMapOf<Int, BigInteger>(0 to BigInteger.ONE, 1 to BigInteger.ONE); 

// * TODO investigate how to do dynamic programming with a pure function ** // 
    private fun calculateFibonacci(n: Int): BigInteger? { 
     if (fibonacciValues.contains(n)) { 
      return fibonacciValues.get(n) 
     } else { 
      val f = calculateFibonacci(n - 2)!!.add(calculateFibonacci(n - 1)) 

      fibonacciValues.put(n, f) 
      return f 
     } 
    } 

Für den gesamten Schnipsel ich diesen Kern hochgeladen: https://gist.github.com/moxi/e30f8e693bf044e8b6b80f8c05d4ac12

Answer 1

Die ganze Sache besteht darin, aus dem imperativen Ansatz herauszubrechen und in Bezug auf die Sequenzmanipulation zu denken.

Im Fall der Fibonacci-Folge, könnte es schwierig sein, weil es sehr verlockend, als eine Folge von Ints zu denken, es aber es, wenn Sie als Folge von Paaren denken es viel einfacher wird (von dem Sie schließlich ableiten eine Folge von Ints)

so könnte man eine unendliche Folge von Paaren schaffen, wo das nächste Paar als zweites Element des vorherigen Paares und einer Summe von Elementen in einem vorherigen Paar definiert ist:

generateSequence(1 to 1) { it.second to it.first + it.second } 
    .map { it.first } 

---

Und ja, Sie können die Tail Call Optimierung nutzen, indem Sie Ihre Methode mit dem Schlüsselwort tailrec markieren - keine Sorge wegen des Stack-Overflows. Sie gilt es kurz vor dem fun Stichwort:

fun fibonacciAt(n: Int) = { 
    tailrec fun fibonacciAcc(n: Int, a: Long, b: Long): Long { 
     return when (n == 0) { 
      true -> b 
      false -> fibonacciAcc(n - 1, a + b, a) 
     } 
    } 

    fibonacciAcc(n, 1, 0) 
} 

Hier weitere Informationen über das ist Tail Recursion in Kotlin.

Answer 2

tut Kotlin implementiert Endaufruf Optimization

Ja, es gibt tailrec Stichwort dafür.

Answer 3

Homegrown:

fun fib(i: Int): Int { 
    tailrec fun go(k: Int, p: Int, c: Int): Int { 
     return if (k == 0) p 
     else go(k - 1, c, p + c) 
    } 

    return go(i, 0, 1) 
} 

generateSequence tatsächlich zeigt eine Fibonacci-Implementierung als Beispiel.

fun fibonacci(): Sequence<Int> { 
    // fibonacci terms 
    // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ... 
    return generateSequence(Pair(0, 1), { Pair(it.second, it.first + it.second) }).map { it.first } 
} 

println(fibonacci().take(10).toList()) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]