Working through category theory for programmers an...

# functional

[Kristian Nedrevold]

Working through category theory for programmers and doing the exercises in Kotlin. What is wrong with this memoize function?

fun <A, B> memoize (f: (A) -> B) = { a: A ->
    val cache = mutableMapOf<A, B>()
    cache.computeIfAbsent(a) { f(a) }
}

[Kristian Nedrevold]

fun main() {
    val toUpperCaseMemoized: (Int) -> Int = memoize(::incrementWithSideEffect)
    toUpperCaseMemoized(1) // Should print
    toUpperCaseMemoized(1) // Should not print
}

fun <A, B> memoize (f: (A) -> B) = { a: A ->
    val cache = mutableMapOf<A, B>()
    cache.computeIfAbsent(a) { f(a) }
}

fun incrementWithSideEffect(n: Int): Int {
    println("I'm a side effect")
    return n + 1
}

[Marian Schubert]

you are creating new mutableMapOf on each call

[Marian Schubert]

so it's always empty

[Kristian Nedrevold]

I guess I can just wrap it in a class then

[Kristian Nedrevold]

class Memoized<in A, out B>(val f: (A) -> B): (A) -> B {
    private val cache = mutableMapOf<A, B>()
    override fun invoke(a: A): B {
        return cache.getOrPut(a) { f(a) }
    }
}

fun <A, B> memoize (f: (A) -> B): (A) -> B = Memoized(f)

[Kristian Nedrevold]

or much cleaner

fun <A, B> memoize (f: (A) -> B): (A) -> B = object : (A) -> B {
    private val cache = mutableMapOf<A, B>()
    override fun invoke(a: A): B {
        return cache.getOrPut(a) { f(a) }
    }
}

[Kristian Nedrevold]

That seems to work

[Marian Schubert]

just move cache out of lambda you are returning

[Kristian Nedrevold]

Oof... so obvious when you said it 🙂 Thanks 🙂