Introduction

Pure functional languages don't have the notion of mutable values and therefore don't have any variable assignment. You only have values and expressions, you can give them names, but you can't change the underlying value for a name.

// you get this behaviour in swift, when using let
let n = 42  
n = 7 // immutable value, reassignment is not allowed  

At first this can be cumbersome, because you can't use many familiar structures that you are used to in imperative languages. One of these structures are loops. Think about a for-loop, you need to increment or decrement a control variable to jump out of the loop at one time. Or take a while-loop, you have to change some state so that the boolean expression evaluates to false and you jump out of the while-loop.

But to implement every computable algorithm you need a form of iteration in the language. So how do functional languages get around this. The answer is simple, they use recursion instead. In this article we will deal with recursive list processing to see how to solve these kinds of problems in a functional way. And we will realize one of the core concepts of functional programming. Building small very generalized functions, reuse and compose them in smart ways to create powerful computations.

The problem domain of list processing

When we do list processing in a recursive way the basic idea is to take the first element of the list (called head) do something with it and recursively call the function again with the rest of the list (called tail). The base case (break condition) of that recursion is the empty list. To reflect this idea about list construction in head and tail, we write the following extension to Swifts Array.

extension Array {  
    func empty() -> Bool {
        return self.count == 0
    }

    var head: Element? {
        get {
            return self.first
        }
    }

    var tail: Array<Element>? {
        get {
            if self.empty() { return nil }
            return Array(self.dropFirst())
        }
    }
}

Lets imagine we want to build a sum function. The imperative way would be to use an accumulator value outside the loop and in each iteration assign the current computation to it.

let values = Array(1...10)  
var sum = 0

for value in values {  
    sum += value
}

print(sum) // 55  

But remember in the functional world there is no value assignment. Instead we pass the accumalator value as a function parameter between calls.

func sum(acc: Int, lst: Array<Int>) -> Int {  
    if lst.empty() { return acc } // base case
    return sum(lst.head! + acc, lst.tail!)
}

We shortly come back to the sum function and explain it in detail. But let me jump to the concept of pure functions first. We will only touch it briefly, but it is important for understanding the next steps.

A pure function is like a mathematical function. When given a certain input it will always produce the same output. The function does not depend on outside state nor is it altering outside state. This is called side effect free or referential transparency. Because the output is always the same for a given input we are able to safely substitute a function call with its resulting value. For example

let n = sum(0, [1,2,3,4,5]) // n is 15  

can safely be written as this

let n = 15  

Mutable values and pure functions simplify the way we reason about our programms. We are able to compute our algorithms with pen and paper, by substituting our expressions and then mathematically verify the correctness of them. Which we will do now with our sum function.

(1) let n = sum(0, [1,2,3])
(2) let n = sum(0 + 1, [2,3])
(3) let n = sum(0 + 1 + 2, [3])
(4) let n = sum(0 + 1 + 2 + 3, [])
// empty list is our base case, so sum will return its accumulator
(5) let n = 0 + 1 + 2 + 3
(6) let n = 6 // correct, sum of 1,2 and 3 is 6

Introducing fold

The above pattern

  • Empty list as base case
  • Split list in head and tail
  • Do something with head and accumulator
  • Call function again with new accumulator and tail
  • Return accumulator when hiting base case

is so common, that the functional world came up with an abstraction for it called fold. Fold implements all the steps above, except the part where it does the actual transformation of the current accumulator. For this we pass a function or closure to fold, which excepts the head of the list and the current accumulator and returns a new accumulator.

You can think of it as if the accumulator is a huge Pacman eating up the list (folds the list) from left to right, element by element and when nothing of the list is left, Pacman can give us the answer to our problem.

And this is how fold looks like in Swift.

func foldl<A,B>(acc: A, list: Array<B>, f: (A, B) -> A) -> A {  
    if list.empty() { return acc }
    return foldl(f(acc, list.head!), list: list.tail!, f: f)
}

The Power of Fold

Now look at a few implementation of common tasks realized with fold. You will quickly notice how versatile it is.

Sum an Array of integers.

func sum(list: Array<Int>) -> Int {  
    return foldl(0, list: list, f: (+))
}

Find the maximum in an Array of integers.

func maximum(list: Array<Int>) -> Int {  
    return foldl(0, list: list, f: max)
}

Compute the factorial of a number.

func fac(n: Int) -> Int {  
    return foldl(1, list: Array(1...n), f: (*))
}

Find out if all values in an Array are true

func universalQuantifier(list: Array<Bool>) -> Bool {  
    return foldl(true, list: list, f: { $0 && $1 })
}

Find out if at least one value in an Array is true

func existencialQuantifier(list: Array<Bool>) -> Bool {  
    return foldl(false, list: list, f: { $0 || $1 })
}

Reverse a list.

extension Array {  
    func push(elem: Element) -> Array<Element> {
        var tmpArray = Array(self)
        tmpArray.insert(elem, atIndex: 0)

        return Array(tmpArray)
    }
}

func reverse<T>(list: Array<T>) -> Array<T> {  
   return foldl(Array<T>(), list: list, f: { return $0.push($1) })
}

Filter elements of an Array.

extension Array {  
    func _append(elem: Element) -> Array<Element> {
        var arr = Array(self)
        arr.append(elem)

        return Array(arr)
    }
}

func _filter<T>(list: Array<T>, pred: (T -> Bool)) -> Array<T> {  
    return foldl(Array<T>(), list: list, f: { pred($1) ? $0._append($1) : $0 })
}

Transform every element of an Array.

func _map<A,B>(list: Array<A>, mf: (A -> B)) -> Array<B> {  
    return foldl(Array<B>(), list: list, f: { $0._append(mf($1)) })
}

Conclusion

Fold is something worth to take a closer look at. Because it shows beautifully how to take an idea that solves one particular problem, abstract out the changing part and make a small, powerfull and highly versatile function to use for any kind of problem from the same domain. This is the essence of functional programming.


  1. Gist of example code
  2. Learn You a Haskell for Great Good!