Sunny Sunny - 4 months ago 12x
iOS Question

Explanation for Swift Memoization Code Signature

To implement a memoized version of a recursive function, one declares the function as a non-mutating variable (per WWDC 2014 - Advanced Swift). For example, the following is the implementation of Fibonacci function:

let fibonacci = memoize { (fibonacci: Int->Double, n: Int) in
n < 2 ? Double(n) : fibonacci(n-1) + fibonacci(n-2)

Can anyone explain what is going on in Swift? For example, how does Swift know that fibonacci takes only one argument in the above code snippet? How does the compiler figure this out? How do we mere mortals figure this out? What does the grammar expression look like in the compiler grammar (Normal Form / CFG)?


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.