Sunny - 8 months ago 53

iOS Question

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)?

Answer

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`

.