Shripada Shripada - 3 months ago 10
Swift Question

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

In session 404, of WWDC 14, Dave Abrahams presents a very interesting version of memoize:

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:-

In Swift2.0 we can have local function definitions and the Memoize can be cleanly implemented thusly-

func Memoize<T:Hashable, U> (body: ((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

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.