Misleading/Wrong example in the documentation about Memoization

[AcartN]

First, thanks for the arrow library.

This issue originated from a conversation in the #arrow channel on the kotlinlang Slack. Here is the link to the thread: Slack Thread

I was quite surprised when reading the documentation and came across the memoize function in arrow. In the documentation, it's illustrated with the Fibonacci sequence, which requires recursive calls. According to the documentation, you can take a simple DeepRecursiveFunction, apply .memoize, and obtain a function in a val that takes care of memoizing all the calls. No need to modify the original function. The promise was so enticing that I decided to test it out myself.

However, I encountered two issues:

1. The code from the documentation doesn't compile as is.
2. After making some slight modifications to make it compile, it doesn't behave as expected at all.

Here are the details for each problem:

1. I copied and pasted the code from the documentation to test it:

   
   import arrow.core.memoize

val fibonacciWorker = DeepRecursiveFunction<Int, Int> { n -> when (n) { 0 -> 0 1 -> 1 else -> callRecursive(n - 1) + callRecursive(n - 2) } }

val fibonacciMemoized = ::fibonacciWorker.memoize()

fun fibonacci(n: Int): Int { require(n >= 0) return fibonacciMemoized(n) }

I am using:
- IntelliJ 2023.2 EAP
- Kotlin 1.8.10
- Gradle Wrapper 7.6
- Arrow 1.2.0-RC
- Compile flags : languageVersion = 1.9 and context receivers enabled.

This code doesn't compile, and the error message is as follows:

e: file:///Users/.../fibo.kt:18:12 Type mismatch: inferred type is DeepRecursiveFunction<Int, Int> but Int was expected

It seems that the `memoize` function doesn't work as expected on a `DeepRecursiveFunction`.

2. Therefore, I modified the code by wrapping the `DeepRecursiveFunction` inside a regular function:

import arrow.core.memoize

val fibonacciWorker = DeepRecursiveFunction<Int, Int> { n -> print(".") // I added this print statement in order to visualize all the recursive calls. when (n) { 0 -> 0 1 -> 1 else -> callRecursive(n - 1) + callRecursive(n - 2) } }

fun fib(n: Int) = fibonacciWorker(n) // wrap the DeepRecursiveFunction in a regular one

val fibonacciMemoized = ::fib.memoize()

fun fibonacci(n: Int): Int { require(n >= 0) return fibonacciMemoized(n) }

// Show that the memoize function actually memoize the call to hat function but not all the recursive calls fun main() { println(fibonacci(4)) // .........3 println(fibonacci(4)) // 3 => has been memoized println(fibonacci(3)) // .....2 => recursive calls have not been memoized }

In this code, it compiles, but it doesn't produce the desired behavior. As shown in the main function, the wrapper function is memoized correctly, but the recursive calls are not. This is completely absurd for an example like the Fibonacci sequence, where memoizing the recursive calls is crucial.

The memoize function remains useful, but it seems that we will still need to manually implement memoization for recursive functions like Fibonacci 😞

[balazstothofficial]

These two helpers would make it easier to create recursive memoized functions:

fun <P, R> memoizedFun(function: (params: P, recurse: (P) -> R) -> R): (P) -> R {
    val memoizedParams = mutableMapOf<P, R>()
    fun memoizedFun(params: P): R = memoizedParams
        .getOrPut(params) { function(params, ::memoizedFun) }

    return ::memoizedFun
}

val memoizedFibonacci: (Int) -> Int = memoizedFun { n, recurse ->
    when (n) {
        0 -> 0.also { println("Should be printed only once if memoized") }
        1 -> 1
        else -> recurse(n - 1) + recurse(n - 2)
    }
}

class MemoizedDeepRecursiveFunction<P, R>(
    private val block: suspend DeepRecursiveScope<P, R>.(P) -> R
) {
    private val memoizedParams = mutableMapOf<P, R>()
    private val deepRecursiveFunction = DeepRecursiveFunction { p ->
        memoizedParams.getOrPut(p) { block(p) }
    }

    operator fun invoke(p: P) = deepRecursiveFunction(p)
}

val memoizedDeepRecursiveFibonacci: MemoizedDeepRecursiveFunction<Int, Int> =
    MemoizedDeepRecursiveFunction { n ->
        when (n) {
            0 -> 0.also { println("Should be printed only once if memoized") }
            1 -> 1
            else -> callRecursive(n - 1) + callRecursive(n - 2)
        }
    }

Maybe they could be included in the library.

[serras]

I've created this PR based on the conversation above. It turns out that we don't even need a separate MemoizedDeepRecursiveFunction class if we play well with the scopes.

[serras]

I've opened this PR https://github.com/arrow-kt/arrow-website/pull/215 to update the docs to point to the new MemoizedDeepRecursiveFunction. Feel free to have a look, and thanks for moving this discussion forward 😄