Memoization

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...