Memoization is a technique to cache results of pure functions. A memoized function behaves as a normal function, but stores the result of previous computations associated with the parameters supplied to produce that result.
The classic example of memoization is Fibonacci:
import arrow.syntax.function.memoize
import kotlin.system.measureNanoTime
fun recursiveFib(n: Long): Long = if (n < 2) {
n
} else {
recursiveFib(n - 1) + recursiveFib(n - 2)
}
fun imperativeFib(n: Long): Long {
return when (n) {
0L -> 0
1L -> 1
else -> {
var a = 0L
var b = 1L
var c = 0L
for (i in 2..n) {
c = a + b
a = b
b = c
}
c
}
}
}
fun main(args: Array<String>) {
var lambdaFib: (Long) -> Long = { it } //Declared ahead to be used inside recursively
lambdaFib = { n: Long ->
if (n < 2) n else lambdaFib(n - 1) + lambdaFib(n - 2)
}
var memoizedFib...