3. More Functional Swift

Closures, Recursion

Previous Posts

1. Learn Swift by running Scripts
2. Functional Swift

Take the each function from the previous post. Simplify it a little such that the callback takes one argument. We will not pass the Array index as argument, only the Array element.

func each<T>(array: [T], callback: (T) -> Void) {
    for elem in array {
        callback(elem)
    }
}
each([1, 2, 3, 4],callback: print)

And here is the output.

$ xcrun swift -i test.swift
1
2
3
4

Now the callback is called for each element of the Array with the corresponding element. We call each with an Array, and print as the callback! We did not write any function for the callback. The callback can be a global function or any function for that matter.

Similarly let us rewrite the map function, from the last post, such that its callback takes only one argument.

func map<T>(array: [T], callback: (T) -> T) -> [T] {
    var newarray: [T] = []
    for elem in array {
        newarray.append(callback(elem))
    }
    return newarray 
}

And let us use it to square each element of an array, and return a new array of the squares.

let inputArray = [1, 2, 3, 4, 5]
let outArray = inputArray.map({(element: Int) -> Int in
    return element * element
})
print(outArray)
// Outputs [1, 4, 9, 16, 25]

Closures

What is going on here? The second argument to map is not a function. Here is what it is.

{(element: Int) -> Int in
    return element * element
}

It is a Closure. A Closure is a function without a name. The parameters and return type are defined within the block and are separated from the rest of the statements by the “in” keyword. A Closure is a function expression, and hence can be used inline anywhere, instead of a function variable. Closures are like anonymous functions or lambdas in other languages.

If the Closure is the last argument to the function, you can write it as a trailing closure outside the function call, shown as below.

let inputArray = [1, 2, 3, 4, 5]
let outArray = inputArray.map() {(element: Int) -> Int in
 return element * element
}
print(outArray)
// Outputs [1, 4, 9, 16, 25]

Since the closure’s type is already available to the compiler from the definition of the map function, you can eliminate the type here in the closure.

let inputArray = [1, 2, 3, 4, 5]
let outArray = inputArray.map() {element in return element * element}
print(outArray)
// Outputs [1, 4, 9, 16, 25]

The arguments to a closure are available within a closure as shorthand as in $0, $1, $2 … etc. So we can shorten our function call even further.

let inputArray = [1, 2, 3, 4, 5]
let outArray = inputArray.map() {$0 * $0}
print(outArray)
// Outputs [1, 4, 9, 16, 25]

If a Closure consists of a single expression, it will return the value of the expression. The return statement can be omitted in this case.

Recursion

Recursion happens when a function calls itself from within itself.

We will re-write the factorial function from article 1 to use recursion instead. We know that

n! = n * (n — 1)!
n! = n * (n — 1) * (n — 2)!
... and so on

And we will use this in our recursive factorial function

func factorial(n: Int) -> Int {
    return n == 0 ? 1 : n * factorial(n — 1)
}
 
print(factorial(5))

Compare this to our earlier function and see how elegant this is!

Look at the ternary conditional operator in Swift.

n == 0 ? 1 : n * factorial(n — 1)

It has three parts, containing three expressions, separated by a ? and :. The first part is a conditional expression, which if evaluates to true, then the whole expression evaluates to the second part, otherwise the third part.

If the conditional n == 0 evaluates to true then 1 is returned. This is known as the break condition of the recursion function. If you don’t have a break condition in a recursive function you will recurse infinitely!

If the conditional n == 0 evaluates to false then,

n * factorial(n — 1)

is returned.

The function calls itself recursively, until n is equal to 0 the break condition.

The fibonacci series calculation is a popular example used to demonstrate recursion in functional programming languages. Each number in the fibonacci series is the sum of the previous two numbers starting after the second number. e.g. 0,1,1,2,3,5,8,13,21 .. etc.

func fib(n: Int) -> Int {
    return n < 2 ? n : (fib(n — 1) + fib(n — 2))
}
print(fib(10))       // prints 55

Below, see what happens in each step.

fib(5) => fib(4) + fib(3)
fib(5) => (fib(3) + (fib(2)) + (fib(2) + fib(1))
fib(5) => ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) +1)
fib(5) => (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) +1)
fib(5) => (((1 + 0) + 1) + (1 + 0)) + (1 + 0) +1)
fib(5) => 5

You will notice the computation involved grows exponentially, larger the number you want to calculate in the series. You will quickly run out of time or stack space or memory. Try it for a large number, be warned though.

Looking at the above you can see fib being called multiple times for the same value. Things can get pretty bad for large numbers. If we could save the returned value, and next time return the saved value, instead of calling the function again, we could change this exponential computation into a linear computation and make it much more efficient.

We will fix this problem later in this series.

Read the next article JSON in Swift.