Need Detailed Explanation for Memoize Implementation in Swift (Wwdc 14, Session 404)

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

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.

Explanation for Swift Memoization Call Syntax

The signature of the memoize function (from that WWDC talk) is:

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

As you can see, it takes in a body function ((T)->U, T) -> U, and it returns another function (T) -> U. You're allowed to use this function with any types you choose in place of T and U, with the restriction that T must be Hashable.

Since the body function here (your trailing closure) is explicitly declared to take ((Int)->Double, Int), the compiler can infer, through complicated constraint-solving, that T == Int and U == Double, so the function returned by memoize is necessarily (Int)->Double.

Swift Algorithm calculate possible way to reach destination

You'll need to employ a technique called dynamic programming.

The idea is to prune entire branches of the call tree by avoiding recursive calls for values that have already been computed.

A dictionary is used to store a mapping from inputs to outputs. Each time a new recursive call is about to be done, the dictionary is first checked to see if it already contains the output for the desired input. If it exists, it's used, otherwise recursion is used to obtain the result. Once computed, the result is then stored in the dictionary for future use.

Here's what that would look like:

var cache = [Int: Int]()

func probabilityToGoal(_ n: Int) -> Int {
    if n == 1 { return 1 }
    if n == 2 { return 2 }
    if n == 3 { return 5 }
    if n == 4 { return 8 }
    if n == 5 { return 14 }
    if n == 6 { return 25 }

    if let existingValue = cache[n] {
        // result for n is already known, just return it
        return existingValue
    }

    let newValue = probabilityToGoal(n-1)
                 + probabilityToGoal(n-2)
                 + probabilityToGoal(n-3)
                 + probabilityToGoal(n-4)
                 + probabilityToGoal(n-5)
                 + probabilityToGoal(n-6)

    cache[n] = newValue // store result for future result

    return newValue
}

print(probabilityToGoal(64))

Keep in mind that this won't work n ≥ 64, because it overflows the 64 bit Int (on 64 Bit systems).

Also, an iterative solution will perform much faster, as it removes recursion overhead and allows you to use an Array instead of a Dictionary:

var cache = [0, 1, 2, 5, 8, 14,25]

func probabilityToGoal2(_ n: Int) -> Int {
    cache.reserveCapacity(n)
    for i in stride(from: n, to: 6, by: +1) {
            let r1 = cache[i - 1] + cache[i - 2]
            let r2 = cache[i - 3] + cache[i - 4]
            let r3 = cache[i - 5] + cache[i - 6]
            cache.append(r1 + r2 + r3)
    }

    return cache[n]
}

How can a closure escape when it's used in a nested function?

This seems to be due to a shortcoming in the component that analyses escaping behaviour; it's apparently a little too defensive.

See this bug report. Current state: Open, Unassigned.

---

Related Topics