Need detailed explanation for Memoize implementation in Swift (WWDC 14, session 404)

Question

Dave Abrahams presents a very interesting version of memoize (WWDC 2014 Session 404: Advanced Swift):

func Memoize<T:Hashable, U> (body: (T -> U, T ) -> U ) -> (T) -> U {

      var memo = Dictionary <T, U> ()

      var result: (T -> U)!

      result = { x in
            if let q = memo[x] { return q }
            let r = body(result, x)
            memo[x] = r
            return r
      }

      return result
}

let factorial = Memoize { (factorial, x) in
                x == 0 ? 1 : x * factorial(x - 1)
        }

===== This works great even for recursive functions. I am having difficulty in actually understanding this. Any expert explanation would greatly help.

Update: using local functions:

Swift 2's local functions allow Memoize to be implemented more cleanly.

Swift 3 requires the @noescaping annotation; otherwise it complains: "Declaration closing over non-escaping parameter body may allow it to escape."

func Memoize<T:Hashable, U> (body: @escaping ((T) -> U, T ) -> U ) -> (T) -> U {

    var memo = Dictionary <T, U> ()

    func result(x : T) -> U {
        if let q = memo[x] { return q }
        let r = body(result, x)
        memo[x] = r
        return r
    }

    return result
}

Answer 1

It's actually a more or less completely standard implementation of memoize. You keep a map (here, a dictionary) of inputs and outputs. If we already have the input in the dictionary, look it up and return the output. If we don't, calculate it, store it in the dictionary, and return it.

The memoize function only has to be called once, because it transforms any function (of the proper type) into a memoized version of that function. From then on, you just call the memoized version. So this is a function that accepts a function as parameter and returns a new function as result. The returned function simply wraps a call to the original function in the memoization that I described in the preceding paragraph.

It's hard to know what else to tell you, because I don't know what part you're finding hard to understand. My book goes into great detail on how functions get passed around in Swift. If you don't understand the notion of passing a function as parameter to a function, read this section. If you don't understand the notion of a function returning a function, read this section.

Swift has closures, so we get to maintain the dictionary in the environment space of the returned function (by defining it outside the returned function, so that it is captured). If that's what you're finding hard to understand, here's a simpler example of that.