Shripada - 9 months ago 31

Swift Question

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.

In Swift2.0 we can have local function definitions and the

`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.