Hello ! I am experimenting with the arrow library...

# arrow

[Nicolas Acart]

Hello !

I am experimenting with the arrow library and I wanted to try the memoize function. I was trying this example from the documentation which is implementing a Fibonacci with DeepRecursiveFunctions and memoize it thanks to arrow. My problem is that the code does not even compile sad panda
I am running it with Kotlin 1.8.10, arrow 1.2.0-RC, languageVersion 1.9 and context receivers enabled. Am I doing something wrong?

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

fun main() {
    println(fibonacci(6))
}

The error :

e: file:///Users/jj/IdeaProjects/ContextDispatcher/src/main/kotlin/fibo.kt:15:12 Type mismatch: inferred type is DeepRecursiveFunction<Int, Int> but Int was expected

I tried to fix it by wrapping the worker into a true function. This way, I am able to make it compile but it is still not memoized :

import arrow.core.memoize

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

fun fib(n: Int) = fibonacciWorker(n)

val fibonacciMemoized = ::fib.memoize()

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

fun main() {
    println(fibonacci(6))
}

The result :

Should be printed only once if memoized
Should be printed only once if memoized
Should be printed only once if memoized
Should be printed only once if memoized
Should be printed only once if memoized
8

Maybe I am doing something wrong but I am a little bit confused 🤔

Any ideas?

[Youssef Shoaib [MOD]]

The example looks wrong as far as I'm aware. It will indeed only memorise calls to fibonacciWorker but not any recursive calls. I think maybe you'd need a separate cache as a Map which you then check the values of.

[Nicolas Acart]

Yep ! You are right
To prove it, I changed the main to :

fun main() {
    println(fibonacci(4))
    println("----")
    println(fibonacci(4))
    println("----")
    println(fibonacci(3))
}

and here is the result:

n: 4
n: 3
n: 2
n: 1
n: 0
n: 1
n: 2
n: 1
n: 0
3
----
3
----
n: 3
n: 2
n: 1
n: 0
n: 1
2

We can see that fibonacci(4) has been memoized but not all the recursive calls. Only the "hat" function is memoized.

The example is very misleading. However, I think the memoize function can still be useful for complex calculations that we only want to perform once. I wonder if it is possible to implement a memoized Fibonacci with a simple .memoize() ? I have the impression that it will be necessary to rewrite the logic of the recursive calls in order to memoize the recursive calls (the old way, without the memoize util function from arrow).

Considering all of this, it might be a good idea to update the documentation. 👀

[Balazs Toth]

I also already stumbled about that. It's not clear that the example is not memoized on recursion. I built this generic helper for memoized recursive 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)
    }
}

[Balazs Toth]

With this you have to copy the implementation of the non-memoized recursive function, but I think it is not really possible otherwise in Kotlin. Since it is not possible to replace the recursive calls otherwise. (Maybe a compiler plugin would work)

[Alejandro Serrano Mena]

we definitely need to improve that section of the docs; could you maybe open an issue with a link to this thread? thank you color

[Nicolas Acart]

Sure @Alejandro Serrano Mena! Here is the issue: https://github.com/arrow-kt/arrow-website/issues/213