An interesting example of using a closure for memoization

Long ago I wrote about the benefits of memoization. It’s a simple idea: a time vs. space trade off. Trade time in CPU for space in memory. A pretty classic example is the massive speed benefit you can get while calculating the Fibonacci sequence by saving values you have already found. (The naive recursive approach recalculates values an exponential number of times.) It’s a toy example but it definitely exhibits the power of the technique.

I have to learn Go for an upcoming project at work. I’m excited about it, and I’ve been starting out by working through the Go Tour lesson series. I was pretty interested to see slide 22 in the more types lesson, an exercise instructing the reader to write a function that calculates Fibonacci numbers using a closure. The way this is set up gently nudges the reader toward writing an answer that uses memoization through a closure.

Here’s what I came up with:

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    a := [10]int{1, 1}
    b := 0
    f := func() int {
        val := a[b]
        if val == 0 {
            val = a[b - 1] + a[b - 2]
            a[b] = val
        }
        b ++
        return val
    }
    return f
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

I really liked the way that the solution uses a built in array and a closure to accomplish memoization. It’s very clean. Coming from doing a lot of PHP it’s nice to see because a fairly standard way of implementing this technique in that language is to use the static keyword which always felt a bit hacky (on a side note, you could do this in PHP, but you’d need the use feature on the closure, which I am also not a fan of). The same technique would definitely work in javascript as well. It’s a welcome addition to my toolset.