functional programming

A persistent tree using indirect enums in Swift

Posted on by airspeedvelocity

UPDATE: now conforms to Swift 2.1b2

Suppose you want an ordered set. Set is great and all, but it’s unordered. You could always use a Set anyway, and sort the contents when needed. Or you could use an array, keep it sorted, and always insert new elements in the right place. Or, you could use a tree.

One way to build a tree in Swift would be with a class that refers to itself. Something like this for a binary search tree:

class Tree<Element: Comparable> {
    let value: Element
    // entries < value go on the left
    let left: Tree<Element>?
    // entries > value go on the right
    let right: Tree<Element>?
}

For the tree’s logic, Element would only have to be Comparable, not Hashable, which is another potential benefit over Set.

The left and right subtrees are optional, with nil at the leaves when there’s no lesser/greater value than the current node. But there’s a problem with this approach – how do you represent an empty tree? value is not optional. Sure you could make it optional, and have an empty tree be represented by a nil value. But that doesn’t feel healthy.

Really, you want an enum with an associated type. Something like this:

enum Tree<Element: Comparable> {
    case Empty
    case Node(Tree<Element>,Element,Tree<Element>)
}

So, a tree is either empty, or it has a left and right subtree and a value. The subtrees no longer need to be optional, because if they’re empty, they can just hold the .Empty value.

No more boxes

Except, this won’t work. Swift enums are value types. So they can’t contain themselves like this. You need some kind of indirection – a reference type, such as a class.

Up until 2.0b4, you would have to use a Box trick – inserting a class in between each enum:

final class Box<Element> {
    let unbox: Element
    init(_ x: Element) { self.unbox = x }
}

enum Tree <Element: Comparable> {
    case Empty
    case Node(Box<Tree<Element>>,Element,Box<Tree<Element>>)
}

Well that’s pretty gross. And we haven’t even got to the actual implementation logic yet. Trust me, Box is gonna stomp all over that code leaving its muddy footprints everywhere.

But good news! The latest release of Swift introduces the indirect keyword for enums. This is similar to a transparent version of the box above, putting a reference where the boxed value would go. Xcode will even suggest putting in the keyword for you.

So now we can write this:

indirect enum Tree<Element: Comparable> {
    case Empty
    case Node(Tree<Element>,Element,Tree<Element>)
}

But really, we want a balanced tree. Simple binary search trees work well with random data, but if you insert already-ordered data into them, they degenerate into a linked list (because all the insertions happen down one side of the tree).

So lets go with a red-black tree – a kind of binary search tree that colours its nodes red or black, and then uses some invariants to guarantee it remains balanced on insertion. If you follow that link you’ll see quite a lot of ugly code for maintaining those invariants – but don’t worry, we’re going to write something that hopefully looks a lot simpler.

So here’s the tree, now with added colour, plus a couple of initializers to make things easier:

enum Color { case R, B }

indirect enum Tree<Element: Comparable> {
    case Empty
    case Node(Color,Tree<Element>,Element,Tree<Element>)

    init() { self = .Empty }

    init(_ x: Element, color: Color = .B,
        left: Tree<Element> = .Empty, right: Tree<Element> = .Empty)
    {
        self = .Node(color, left, x, right)
    }
}

Some might not like that I called my Color cases R and B instead of Red and Black. It’s a personal preference, but I like to keep them shorter because a) they’re arbitrary – they are only called that because those were the two colours on the laser printer they had at Xerox PARC, and b) it keeps the pattern matching shorter and (therefore, IMO) clearer. Judge for yourself when we get to that part.

By the way, this implementation is a Swift translation of an ML version from Chris Okasaki’s Purely Functional Data Structures which is definitely worth reading if you like this kind of stuff. What’s cool is that with the new 2.0 features of Swift, the Swift version is getting pretty close to the ML one in terms of expressivity/simplicity.

Checking if the tree contains an element

So, let’s start with contains. This needs to recur down the tree, checking each value to see if it’s empty, or if not, whether its value is less than, greater than or equal to the value we’re looking for.

Ideally I would write this using a guard statement like so:

extension Tree {
    func contains(x: Element) -> Bool {
        guard case let .Node(_,left,y,right) = self
          else { return false }

        if x < y { return left.contains(x) }
        if y < x { return right.contains(x) }
        return true
    }
}

I like how guard helps here. It lets us unpack the important stuff used by the main body of the function (is it a node? If so, grab the left, right and value elements – discarding color, since its not important). But it also lets us put the failure case – if you hit an empty node, you know the tree does not contain the element – up front. Then, head left if the element we’re looking for is less than this one, or right if it’s greater.

We can rely on the fact that Comparable elements are required to be in a strict total order. This means if x is neither less than or greater than a value, it must be equal to that value. So we’ve found the element and contains is true.

Inserting an element

OK, insert is a little trickier. We’re going to define insert as a method that returns a new tree – one with the new value inserted. This is a little different to Set.insert, which is an in-place insert.

In doing this, we’re going to create a “persistent” data structure – one that does not change the old structure when it updates it. This might sound like multiple insertions in a row are going to perform many unnecessary copies of the whole structure, but it isn’t necessarily that bad. Because nodes of the tree are read-only, two trees can share nodes. Only the nodes that are actually changed as a result of the insert need to be copied.

First, the insert method. It doesn’t really do much except maintain one of the invariants required to maintain balance: the root node must always be black. It leaves most of the work to a second function, ins:

private func ins<T>(into: Tree<T>, _ x: T) -> Tree<T> {
    guard case let .Node(c, l, y, r) = into
        else { return Tree(x, color: .R) }

    if x < y { return balance(Tree(y, color: c, left: ins(l,x), right: r)) }
    if y < x { return balance(Tree(y, color: c, left: l, right: ins(r, x))) }
    return into
}


extension Tree {
    func insert(x: Element) -> Tree {
        guard case let .Node(_,l,y,r) = ins(self, x)
            else { fatalError("ins should never return an empty tree") }

        return .Node(.B,l,y,r)
    }
}

So, if we’ve hit an empty node, append the value here as a new node. New nodes are always red.

Otherwise, insert the value into the left or right subtree. And if the element is equal, stop and don’t insert anything, since we’re implementing set behaviour here.

But there’s also the call to balance. This function is going to ensure that, as we come back up the tree having inserted our new element, the tree is properly balanced, by looking at whether any invariants have been broken and fixing them.

This is normally where the ugliness of implementing a red-black tree resides. But we’re going to use Swift’s pattern matching to try and keep it simple. The balancing logic can be summarized as: “on the way back up from an insertion, if there’s a black node, with a red child and a red grandchild, this needs fixing”.

A red child and grandchild of a black node can happen in one of four different configurations. Here’s a visualization of one of those possibilities (excuse the ASCII art):

        z: black
       /        \
      x: red     d
     / \
    a   y: red
       / \
      b   c

needs rearranging into:

         y: red
       /        \
      x: black   z: black
     / \        / \
    a   b      c   d

Once you understand this visualization, you can then encode it into a Swift pattern matching if statement, that extracts all the relevant variables from the possible imbalanced structure, then returns them reconfigured as the second, balanced, version.

The above re-balancing operation would end up encoded in Swift like this:

case let .Node(.B, .Node(.R, a, x, .Node(.R, b, y, c)), z, d):
    return .Node(.R, .Node(.B, a, x, b), y, .Node(.B, c, z, d))

This is why I prefer .B and .R for the colour case names – single-letter names to me look clearer in this stage, which is when they matter. There’s no getting around it, the transformation code is going to be hard to read no matter what you do, so the best you can hope for is easy translation. The longer words wouldn’t help with the key problem, which is encoding the diagram above into a pattern-matching statement.

To write the full balancing function, you need to visualize all 4 imbalanced configurations, then encode them into 4 patterns. If a node doesn’t match any, it’s good and you can return it as-is:

private func balance<T>(tree: Tree<T>) -> Tree<T> {
    switch tree {
    case let .Node(.B, .Node(.R, .Node(.R, a, x, b), y, c), z, d):
        return .Node(.R, .Node(.B,a,x,b),y,.Node(.B,c,z,d))
    case let .Node(.B, .Node(.R, a, x, .Node(.R, b, y, c)), z, d):
        return .Node(.R, .Node(.B,a,x,b),y,.Node(.B,c,z,d))
    case let .Node(.B, a, x, .Node(.R, .Node(.R, b, y, c), z, d)):
        return .Node(.R, .Node(.B,a,x,b),y,.Node(.B,c,z,d))
    case let .Node(.B, a, x, .Node(.R, b, y, .Node(.R, c, z, d))):
        return .Node(.R, .Node(.B,a,x,b),y,.Node(.B,c,z,d))
    default:
        return tree
    }
}

Note, this pattern match recurses 3 levels deep into the enum. This is also where getting rid of Box was critical. It seriously gets in the way – here is how it would look before indirect:

if case let .Node(.B,l,z,d) = tree, case let .Node(.R,ll,y,c) = l.unbox, case let .Node(.R,a,x,b) = ll.unbox {
    return .Node(.R, Box(.Node(.B,a,x,b)),y,Box(.Node(.B,c,z,d)))
}

Note, the return statement is the same in all 4 rebalance patterns. It’s only the pattern match that changes, based on which of the 4 imbalance possibilities is being checked.

It might be nice to be able to group these 4 possible matches together like so:

    switch tree {
    case let .Node(.B, .Node(.R, .Node(.R, a, x, b), y, c), z, d),
             .Node(.B, .Node(.R, a, x, .Node(.R, b, y, c)), z, d),
             .Node(.B, a, x, .Node(.R, .Node(.R, b, y, c), z, d)),
             .Node(.B, a, x, .Node(.R, b, y, .Node(.R, c, z, d))):
        return .Node(.R, .Node(.B,a,x,b),y,.Node(.B,c,z,d))
    default:
        return tree
    }

but Swift won’t allow multiple patterns in a case when the pattern declares variables, so we have to stick with the multiple returns for now.

Traversing in-order

So, now we have a nice balanced tree. But to get the benefit of an ordered set, we want to iterate over it in order. This sounds like a job for SequenceType. That way, you could use for...in over the sorted elements.

In-order traversal of a tree is usually done recursively, but that’s a little tricky to do when you want to give anyGenerator a closure expression that spits out the next element. So instead, we can use a stack to do it iteratively:

extension Tree: SequenceType {
    func generate() -> AnyGenerator<Element> {
        var stack: [Tree] = []
        var current: Tree = self

        return anyGenerator { _ -> Element? in
            while true {
                // if there's a left-hand node, head down it
                if case let .Node(_,l,_,_) = current {
                    stack.append(current)
                    current = l
                }
                // if there isn’t, head back up, going right as
                // soon as you can:
                else if !stack.isEmpty, case let .Node(_,_,x,r) = stack.removeLast() {
                    current = r
                    return x
                }
                else {
                // otherwise, we’re done
                return nil
                }
            }
        }
    }
}

Initializing from another sequence

One last extension. When you have a container, it’s nice to be able to initialize it from another sequence, as well as from a literal. These are both pretty easy:

extension Tree: ArrayLiteralConvertible {
    init <S: SequenceType where S.Generator.Element == Element>(_ source: S) {
        self = source.reduce(Tree()) { $0.insert($1) }
    }

    init(arrayLiteral elements: Element...) {
        self = Tree(elements)
    }
}

Given these, you can now create new sets using literal syntax:

let alphabet = Tree("the quick brown fox jumps over the lazy dog".characters)
let primes: Tree = [2, 3, 5, 7, 11, 13, 17, 19]

That’s it for now. Several features of Swift 2.0 make this code a lot more pleasant to read and write. There are various further enhancements you could make. The tree maybe ought to be wrapped in an outer struct to avoid exposing the enum implementation. The next logical extension would be conforming to CollectionType.

And there are also performance improvements you could make (the functional data structures book suggests a few as exercises). Honestly, the times when this data structure will do better than an unordered set or array + sort are probably going to be pretty rare. But it’s nice to have the option now.

Below is the final code, along with some tests, or you can find the full code for the tree in a gist, here.

If you found this interesting (and if you made it all the way down here, hopefully that’s true!), it’ll be part of Chris Eidhof and my book, which you can get a preview of here.

enum Color { case R, B }

indirect enum Tree<Element: Comparable> {
    case Empty
    case Node(Color,Tree<Element>,Element,Tree<Element>)
    
    init() { self = .Empty }
    
    init(_ x: Element, color: Color = .B,
        left: Tree<Element> = .Empty, right: Tree<Element> = .Empty)
    {
        self = .Node(color, left, x, right)
    }
}


extension Tree {
    func contains(x: Element) -> Bool {
        guard case let .Node(_,left,y,right) = self
            else { return false }
        
        if x < y { return left.contains(x) }
        if y < x { return right.contains(x) }
        return true
    }
}

private func balance<T>(tree: Tree<T>) -> Tree<T> {
    switch tree {
    case let .Node(.B, .Node(.R, .Node(.R, a, x, b), y, c), z, d):
        return .Node(.R, .Node(.B,a,x,b),y,.Node(.B,c,z,d))
    case let .Node(.B, .Node(.R, a, x, .Node(.R, b, y, c)), z, d):
        return .Node(.R, .Node(.B,a,x,b),y,.Node(.B,c,z,d))
    case let .Node(.B, a, x, .Node(.R, .Node(.R, b, y, c), z, d)):
        return .Node(.R, .Node(.B,a,x,b),y,.Node(.B,c,z,d))
    case let .Node(.B, a, x, .Node(.R, b, y, .Node(.R, c, z, d))):
        return .Node(.R, .Node(.B,a,x,b),y,.Node(.B,c,z,d))
    default:
        return tree
    }
}


private func ins<T>(into: Tree<T>, _ x: T) -> Tree<T> {
    guard case let .Node(c, l, y, r) = into
        else { return Tree(x, color: .R) }

    if x < y { return balance(Tree(y, color: c, left: ins(l,x), right: r)) }
    if y < x { return balance(Tree(y, color: c, left: l, right: ins(r, x))) }
    return into
}


extension Tree {
    func insert(x: Element) -> Tree {
        guard case let .Node(_,l,y,r) = ins(self, x)
            else { fatalError("ins should never return an empty tree") }

        return .Node(.B,l,y,r)
    }
}



extension Tree: SequenceType {
    func generate() -> AnyGenerator<Element> {
        var stack: [Tree] = []
        var current: Tree = self

        return anyGenerator { _ -> Element? in
            while true {
                // if there's a left-hand node, head down it
                if case let .Node(_,l,_,_) = current {
                    stack.append(current)
                    current = l
                }
                // if there isn’t, head back up, going right as
                // soon as you can:
                else if !stack.isEmpty, case let .Node(_,_,x,r) = stack.removeLast() {
                    current = r
                    return x
                }
                else {
                // otherwise, we’re done
                return nil
                }
            }
        }
    }
}

extension Tree: ArrayLiteralConvertible {
    init <S: SequenceType where S.Generator.Element == Element>(_ source: S) {
        self = source.reduce(Tree()) { $0.insert($1) }
    }
    
    init(arrayLiteral elements: Element...) {
        self = Tree(elements)
    }
}

import Darwin

extension Array {
    func shuffle() -> [Element] {
        var list = self
        for i in 0..<(list.count - 1) {
            let j = Int(arc4random_uniform(UInt32(list.count - i))) + i
            guard i != j else { continue }
            swap(&list[i], &list[j])
        }
        return list
    }
}


let engines = [
    "Daisy", "Salty", "Harold", "Cranky",
    "Thomas", "Henry", "James", "Toby",
    "Belle", "Diesel", "Stepney", "Gordon",
    "Captain", "Percy", "Arry", "Bert",
    "Spencer",
]

// test various inserting engines in various different permutations
for permutation in [engines, engines.sort(), engines.sort(>),engines.shuffle(),engines.shuffle()] {
    let t = Tree(permutation)
    assert(!t.contains("Fred"))
    assert(t.elementsEqual(t.insert("Thomas")))
    assert(!engines.contains { !t.contains($0) })
    assert(t.elementsEqual(engines.sort()))
    print(t.joinWithSeparator(","))
}

Protocol extensions and the death of the pipe-forward operator

Posted on by airspeedvelocity

So a while back I wrote about using some functional programming techniques in Swift to solve the Luhn credit card checksum problem.

One of the suggestions in the article was defining and using |> to avoid the annoying tennis-match bouncing left and right between free functions and methods.

Since 2.0 came out, I’ve been thinking I really needed to update some of my articles to the new syntax, and started on this one. Except as protocol extensions are the new hotness, using them would probably be the more “Swift-y” way of writing this. So here’s a solution using new 2.0 features.

As a reminder, here’s the requirements, in the form of wikipedia’s description of the algorithm:

  1. From the rightmost digit, which is the check digit, moving left, double the value of every second digit; if the product of this doubling operation is greater than 9 (e.g., 8 × 2 = 16), then sum the digits of the products (e.g., 16: 1 + 6 = 7, 18: 1 + 8 = 9).
  2. Take the sum of all the digits.
  3. If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; else it is not valid.

So, here in turn are each of the components, all written as extensions.

First, converting characters to integers. Similar to String.toInteger becoming Int.init(String), here’s an extension of Int:

extension Int {
    init?(c: Character) {
        guard let i = Int(String(c)) else { return nil }

        self = i
    }
}

Here I’m using guard to check the value is convertible and return nil if not. Yes, I know, this is hardly different from an if let/else, but I like the use of guard whenever I want to handle a failure case like this “up front”.

It would be nice to make this a protocol extension rather than an extension of Int. All the std lib integer types support a from-string initializer, after all. But this would involve creating a protocol like IntegerStringConvertible and then extending all the integers to conform to it, since such a common grouping doesn’t exist.

The previous post defined mapSome, which takes a transformation function that returns an optional, and returns an array of only those values that weren’t transformed into nil:

extension SequenceType {
    func mapSome<U>(transform: Generator.Element -> U?) -> [U] {
        var result: [U] = []
        for case let x? in lazy(self).map(transform) {
            result.append(x)
        }
        return result
    }
}

(the for case let x? is using the new pattern-matching syntax that lets you for over only the non-nil values in a sequence)

But as of 2.0, flatMap has been enhanced to do this exact thing. So we no longer need to define it.

We’re going to use this along with the character-to-integer initializer to extract only the numbers from the credit-card string, like so, using the new 2.0b2 feature of using an init as a function:

":123-456:".characters.flatMap(Int.init)
// returns [1,2,3,4,5,6]

(note, we have to do this on the .characters view now, since String is no longer itself a sequence).

Next, the a function that let you apply a transformation only to every n th value in a sequence:

extension SequenceType {
    func mapEveryNth(n: Int, transform: Generator.Element -> Generator.Element)
        -> [Generator.Element]  {

            // enumerate starts from zero, so for this to work with the nth element,
            // and not the 0th, n+1th etc, we need to add 1 to the ifIndex check:
            let isNth = { ($0 + 1) % n == 0 }

            return enumerate().map { i, x in
                isNth(i) ? transform(x) : x
            }
    }
}

Then, a sum on any sequence that contains integers:

extension SequenceType where Generator.Element: IntegerType {
    func sum() -> Generator.Element {
        return reduce(0, combine: +)
    }
}

and an extension on any integer to check if it’s a multiple of another:

extension IntegerType {
    func isMultipleOf(of: Self) -> Bool {
        return self % of == 0
    }
}

And finally, to put them all together into a single extension to String that validates the checksum:

extension String {
    func luhnchecksum() -> Bool {
        return characters
            .flatMap(Int.init)
            .reverse()
            .mapEveryNth(2) { $0 < 5 ? $0*2 : $0*2 - 9 }
            .sum()
            .isMultipleOf(10)
    }
}

let ccnum = "4012 8888 8888 1881"
print( ccnum.luhnchecksum() ? "👍" : "👎" )

This now looks very similar to the version that used the |> operator – but without having to define any custom operator at all. Which feels like a win to me.

Yes, you could have done all this before using extensions of concrete objects in 1.2. But most of these extensions are more general than that – for example, mapSome can work on the string character view, but also arrays, dictionaries, sets.

Anyway, now back to playing with beta 2…

zipWith, pipe forward, and treating functions like objects

Posted on by airspeedvelocity

In the previous article, about implementing the Luhn algorithm using function composition in Swift, I had a footnote to the part about using mapEveryNth to double every other digit:

An alternative could be a version of map that cycled over a sequence of different functions. You could then give it an array of two functions – one that did nothing, and another that did the conversion.

This post is about doing just that. I’ll define some more generic helper functions, and then use them to build a variant of our checksum function.

First up: cycling through a sequence multiple times. Suppose you have a sequence, and you want to repeat that sequence over and over. For example, passing in 1...3 would result in 1,2,3,1,2,3,1,...etc.

You could do this by returning a SequenceOf object that takes a sequence, and serves up values from its generator, but intercepts when that generator returns nil and instead just resets it to a fresh one:

func cycle
  <S: SequenceType>(source: S) 
  -> SequenceOf<S.Generator.Element> {
    return SequenceOf { _->GeneratorOf<S.Generator.Element> in
        var g = source.generate()
        return GeneratorOf {
            if let x = g.next() {
                return x
            }
            else {
                g = source.generate()
                if let y = g.next() {
                    return y
                }
                else {
                    // maybe assert here, if you want that behaviour
                    // when passing an empty sequence into cycle
                    return nil
                }
            }
        }
    }
}

// seq is a sequence that repeats 1,2,3,1,2,3,1,2...
let seq = cycle(1...3)

This code does something that might be considered iffy – it re-uses a sequence for multiple passes. Per the Swift docs, sequences are not guaranteed to be multi-pass. However, most sequences you encounter from day-to-day are fine with multiple passes. Collection sequences are, for example. But some non-collection sequences like StrideThrough ought to be too. My (possibly misguided) take on this: it seems OK to take multiple passes over a sequence, so long as you make it clear to the caller that this will happen. The caller needs to know if their sequence allows this, and if they pass a sequence that doesn’t support it, the results would be undefined.1

OK, next, suppose you have two sequences. Maybe they’re both finite, maybe one is finite and one infinite (such as a sequence created by cycle above). You want to combine the elements at the same point in each one together, using a supplied function that takes two arguments. We’ll call that zipWith, and it’s very simple:

func zipWith
  <S1: SequenceType, S2: SequenceType, T>
  (s1: S1, s2: S2, combine: (S1.Generator.Element,S2.Generator.Element) -> T) 
  -> [T] {
    return map(Zip2(s1,s2),combine)
}

// returns an array of 1+1,2+2,3+3,4+4,5+5,
// so [2,4,6,8,10]
zipWith(1...5, 1...5, +)

How does this work? Zip2 is a SequenceType that takes two sequences, and serves up elements from the same position in each as a pair.2 For example, if you passed it [1,2,3] and ["a","b","c"], Zip2 would be a sequence of (1,"a"), (2,"b"), (3,"c"). If one sequence is longer than the other, Zip2 stops as soon as it’s used up the shortest sequence.3

Then, that zipped sequence of 2-tuples is passed into map, along with the combiner function. Map does it’s thing, calling a transformation function on each element to produce a new combined value. Remember, Swift functions that take n arguments can instead take one n-tuple. That is, if you have a function f(a,b), and a pair p = (x,y), you can call f as f(p). So if Zip2 produces p = (1,1), then +(p) returns 2.

Finally, map spits out the array of combined pairs, and that’s returned.

So, we have a function that cycles over a given sequence forever, and a function that takes two sequences and combines their elements using a given function. How does this help double every other number in a sequence?

Well, suppose you had a sequence of two functions: one that did nothing, just returned its input unchanged, and one that doubled its input. If you cycled that sequence, you’d have an infinite sequence of functions that alternated between doing nothing and doubling.

How could zipWith be used to combine that cycling pair of functions, with a sequence of numbers, such that every other number was doubled? What would the combiner function need to be? It would have to take a value (the number), and a function (do-nothing or double), and apply the function to the number.

We’ve already written a function that does that, last time: pipe forward.

infix operator |> {
    associativity left
}

public func |> <T,U>(t: T, f: T->U) -> U {
    return f(t)
}

So, if we passed in pipe forward as the function to zipWith, it’d do exactly what we want:4

// a function that does nothing to its input
func id<T>(t: T) -> T {
    return t
}

// a function that doubles its input
func double<I: IntegerType>(i: I) -> I {
    return i * 2
}

// an array of those two functions, for Ints:
let funcs: [Int->Int] = [id, double]

// double every other number from one to ten
// returns [1,4,3,8,5,12,7,16,9,20]
zipWith(1...10, cycle(funcs), |> )

Finally, let’s implement the new checksum function. We’re going to re-use the •, mapSome, toInt, sum and isMultipleOf functions from the previous article, just redefining the digit-doubling part:

let doubleThenCombine = { i in
    i < 5
        ? i * 2
        : i * 2 - 9
}

let idOrDouble: [Int->Int] = [
    id,
    doubleThenCombine,
]

let doubleEveryOther: [Int]->[Int] = { zipWith($0, cycle(idOrDouble), |> ) }

let extractDigits: String->[Int] = { mapSome($0, toInt) }

let checksum = isMultipleOf(10) • sum • doubleEveryOther • reverse • extractDigits

let ccnum = "4012 8888 8888 1881"
println( checksum(ccnum) ? "👍" : "👎" )

This shows another benefit of the function composition approach. We completely changed the way the doubleEveryOther function was implemented, but because its interfaces in and out remained the same, everything else could stay untouched. Compare this with the iterative version, where looping and doubling and summing were all tangled up together.

So that’s nice, but you might ask if this version is any better than the version from the last post that used mapEveryNth. And it probably isn’t.

But what it does do is show the power of treating functions like any other object, storing them in a collection and iterating over them.

Suppose the Luhn algorithm actually required you to double the even-positioned numbers, but halve the odd ones. Using the mapIfIndex function, you’d need to take two passes (or write another function that took two transformations). With the zipWith technique, all you’d have to do is replace id with a function to halve its input.

You could take this even further. In this example, the array was built literally. But imagine a scenario where you needed more dynamic behaviour – where the array of functions you passed into zipWith were built at runtime, perhaps chosen via user interaction.

“Big whoop,” you say. “This is just like an array of delegates. I’ve been doing this for years.” And that’s totally fair. But functions can be both lighter-weight and more flexible. No need to create an interface, define methods, create an object that implements the interface, worry about which methods need real implementations and which just need stubbing out. The callee defines the function type, the caller writes a closure expression, maybe captures a few variables, and we’re done. For more on this, see Peter Norvig’s slides on how language features can make design patterns invisible or simpler.5

As ever, you can find all the general-purpose functions defined in this post in the SwooshKit framework.

  1. The alternative to this (which the Swift docs actually advocate) is to only write cycle against collections, not sequences. But this seems like a shame, as it’d rule out using it on sequences that don’t have collection equivalents, like strides, but that ought to be multi-pass capable. Perhaps an option is to create a new protocol, MultipassSequenceType: SequenceType { } and to have sequences that can be used this way extend that? ↩
  2. Zip2 is a bit of an anomoly in the Swift standard library. Whereas in most places, the pattern is to have a function that returns an object (for example, the enumerate function returns an instance of EnumerateSequence), Zip2 skips that stage and is just a struct itself, that you initialize with two sequences. Its usage looks almost exactly the same, but that’s why the Z is capitalized (because the convention is to capitalize the names of structs). ↩
  3. If you’re interested in a version of zip that runs to the end of the longer sequence, I used one in this gist. ↩
  4. If you’re of a more Haskelly temperament, you might feel this is the wrong way around (functions should come before values because f(x). In which case you’d want pipe backwards (<|) and flip the first two arguments. ↩
  5. OK, so he was talking about dynamic languages, not just functional ones, but it’s still worth reading. ↩

A better way to hit bottom

Posted on by airspeedvelocity

After my previous post on finding minimums, a couple of people pointed out that reduce would be much better suited to the task. They’re absolutely right, but I ignored that for the last post since I had another agenda. Plus, the combination of min and reduce is an interesting one with its own wrinkles, that deserves a post of its own, so here it is.

reduce takes a sequence, a starting value, and a combining function, and uses that function to boil the sequence down to a single value. For example, to total up the values in an array:

let a = [2, 4, 6, 8]
// starting with 0, add each value
// of 'a' to a running total
let sum = reduce(a, 0, +)
// sum = 20

That certainly sounds like what we want for finding the minimum value in a sequence, with min as the combining function (as recently made possible in beta 3):

let a = [5, 4, 3, 8]
// but what to put in the starting value?
let the_min = reduce(a, ???, min)

We need to pick a starting value to use on the first call to min. Unlike with addition, there’s no natural constant to start a search for a minmum value. You could start with the maximum value for an Int, but that smells like a hack.

Using the first element of the sequence would do it:

var gen = a.generate()
if let first = gen.next() {
    reduce(a, first, min)
}

But this means the first thing this code does every time is redundantly compare the first element to itself. Strictly speaking, that’s fine from a functional behaviour point of view, and even the performance consequences amortize to negligible, but it’s not very satisfying.

This version avoids that problem:

var gen = a.generate()
if let first = gen.next() {
    reduce(gen, first, min)
}

Why does that work? Because Array.GeneratorType happens to be both a Generator and a Sequence. In fact, in a quick scan through the Swift standard library, I couldn’t spot any generator that wasn’t also a sequence. But just because they always are doesn’t mean they have to be, which is why implementing a generic function tail that returns all but the first element of a sequence is surprisingly tricky – but let’s leave that for a later post.

So, armed with our ability to use reduce to find a minimum, let’s implement our solution from the previous post that finds the minimum numeric value in an array of strings:

let string_ints = ["dog", "12", "cat", "4", "200", "elephant"]

var gen = string_ints.generate()
if let first = gen.next() {
    reduce(gen, first) { (lhs, rhs) in
        switch (lhs.toInt(), rhs.toInt()) {
        case (_, nil): return lhs
        case (nil, _): return rhs
        case (let i, let j): return i < j ? lhs : rhs
        }
    }
}

OK that works, but this is pretty ugly with the generator on top of that convoluted closure. And remember last time I mentioned there were still a couple of issues – if string_ints contains no integer strings, it’ll just return the first non-integer string. And it does every integer conversion twice.

Do we still need the generator? Our closure that chooses between sequence elements now discards nil values as soon as it finds a non-nil one. That means that we could supply nil as our initial argument. This also means a returned value of nil could stand in for “not found”, either because the sequence was empty, or because it contained no strings convertible to numbers.

But before we make that change, let’s neaten things up by pulling out the code that does the nil discrimination into its own function.

Here is combineMaybe, a function that takes a function that combines two values (like min), and returns a new function that chooses between two optionals, always preferring the non-nil one before resorting to the supplied function if neither value is nil:1 2

func combineMaybe<T>
  ( combine: (T,T)->T ) 
  -> (T?,T?)->T? {
    return { lhs, rhs in
        switch(lhs, rhs) {
        case (_, nil): return lhs
        case (nil, _): return rhs
        default: return combine(lhs!,rhs!)
        }
    }
}

combineMaybe is a function decorator – a function that takes another function, and enhances it in some useful way, returning the enhanced function.

We can now use the standard library version of min, enhanced with our decorator, as the combiner function to reduce, supplying nil as the starting value. An initial call to map to first convert the strings to integers generates the input sequence:

let string_ints = ["dog", "12", "cat", "4", "200", "elephant"]
let maybe_ints = map(string_ints) { $0.toInt() }

if let the_min = reduce( maybe_ints, nil, combineMaybe(min)) {
    // the_min = 4
}
else {
    // handle both empty input or no numerics in input
}

This fixes the bug of returning a non-numeric string when that’s all the sequence contains. And it only converts each number once, in the call to map.3 4

If instead we wanted to pull out the maximum values, all that is needed is to replace the passing of min into combineMaybe with max, with everything else remaining the same.

In fact, it’ll even work with other binary functions as well. If you replaced min with +, it’ll add all the numeric values in the array, while still giving you a chance to catch if no numbers were found in the sequence (sometimes zero is still not the right answer for an empty sequence, even one containing integers rather than strings).

  1. The “maybe”-based name comes from Haskell, where maybe is a function that takes a default value, a function, and an optional type (which are called Maybe types). ↩
  2. As ever, really wishing switch was an expression that returned the value of its cases when they were single expressions. ↩
  3. Ok, so this doesn’t fulfil the original requirement of returning a string rather than an integer (from the previous article). I think we can keep that as a subsequent step, I was mostly being antagonistic about that part. ↩
  4. Haskell also has a function, mapMaybe, that is like a map to an optional value, followed by a filter that removes all the resulting nil values. That would be a good building block for solving this problem too, though it still wouldn’t help with the starting value for reduce. ↩

Always write a generalized version of your algorithm

Posted on by airspeedvelocity

Suppose you want to find the minimum value in an array. Well, the Swift standard library has you covered:

let a = [6, 2, 4, 7, 8, 10]
minElement(a)  // returns 2

Ok that’s cool. But suppose you have an array of strings of integers and you want the minimum numeric value.

Well, I guess you could map them to Int and then use the same function:

let a = ["6", "2", "4", "7", "8", "10"]
minElement( a.map { $0.toInt() })

Nope, compiler error. String.toInt returns an Int?, because maybe the string isn’t a number.

Fair enough. I happen to know with my intimate knowledge of the problem domain that we can just ignore non-numeric values. So maybe filter those out?

minElement( a.map { $0.toInt() }.filter { $0 != nil } )  // hmmm

Nope, more compiler errors, because now we have only non-nil values, but they’re still optionals and an Int? doesn’t conform to Comparable. So maybe another map to force-unwrap the results (force unwrap is OK because the filter will guarantee no non-nil elements):1

minElement( a.map{ $0.toInt() }.filter { $0 != nil }.map { $0! } )  // yuck

Ok that compiles now and does return the minimum numeric value. But what if we wanted the result to still be a string?

"\(minElement( a.map{ $0.toInt() }.filter { $0 != nil }.map { $0! } ))" // bleurgh

That’s pretty horrible, and at this point I’m thinking of registering GiveUpAndUseAforLoop.com,2 and Marco Arment is yelling at you kids with your new language to get off his lawn.

Really, what we need is for minElement to take a predicate instead of only using the default <. It doesn't (mutter, grumble) but if it did, we could write this:

minElement(a) {
    switch ($0.toInt(), $1.toInt()) {
    case (_, nil): return true
    case (nil, _): return false
    case (let i, let j): return i < j
    }
}

Ahh. Faith in the functional programming style restored.3 This takes each element, checks if the toInt() of either is nil using pattern matching, always preferring the non-nil version, and if neither are, compares them. Since all it's doing is comparing the converted value, not returning one, the minimum returned is a string.4

There's nothing stopping you from implementing your own overload of Apple's minElement that takes a predicate:5

func minElement
  <E, R: Sequence
  where E == R.GeneratorType.Element>
  (range: R, pred: (E,E)->Bool) -> E {

    var gen = range.generate()
    var min_so_far = gen.next()!

    while let next = gen.next() {
        if(pred(next,min_so_far)) {
            min_so_far = next
        }
    }

    return min_so_far
}

This version copies the Swift library version's questionable practice of exploding in flames if you pass it an empty sequence – the (better?) alternative being make the return value optional to force the caller to acknowledge this possibility.

The moral here is that if you ever write a high-order function, write it as generally as possible. It's only a few extra lines to declare the common case using the general case:6

func minElement
  <E: Comparable, R: Sequence
  where E == R.GeneratorType.Element>
  (range: R) -> E {
    return myMinElement(range, <)
}

Apple does this for most functions (such as sort), just not minElement. But then it is only beta 3, hang in there.

  1. “I thought it was guaranteed not to be nil at this point” is what you could write to the log file in the outer exception handler you can’t have. ↩
  2. Just kidding, I didn’t think about it, I registered it straight away. ↩
  3. This code would be even neater if the Swift switch statement would implicitly return the values of single-line cases, i.e. if all the returns in that closure were removed, the switch would evaluate to the value of the selected case statement, and the closure would return it. They closed my radar as a dupe of 16169366 (don't file another duplicate though). ↩
  4. It's still not perfect – if none of the elements are numeric, it'll return the first one. Also, it'll convert each element twice. Hold that thought for a later post though. ↩
  5. Actually, there might be some compiler bugs stopping you, but I'll leave you to discover those on your own. ↩
  6. If the language would let you, you could even default the last parameter to <, but it won't, so you can't. More dynamic default arguments (including ones derived from other arguments to the same function) could be pretty useful in cutting down the amount of code you need to write for these general- and special-case versions. ↩

Implementing some Ruby builtins in Swift

Posted on by airspeedvelocity

Type 1. into irb and hit tab, and it’ll ask you if you want to see all 105 possibilities. Try it with [ ] and you’ll be offered 155. Ruby comes with a lot of built-in methods on its default types.

It’s debatable how useful all of these are. The idiom in Swift seems much more to be like in the C++ STL, where there are algorithms that operate on collections, rather than collections having methods that operate on themselves. To see more about this, read this article on writing algorithms against collections.

But for the sake of looking at a few Swift language features, let’s implement some of the Ruby popular ones. Maybe they’d be useful making a Ruby refugee feel at home.

First off, the Int loops. Lots of “hey look, ruby is cool” intros kick off with this one:

10.times do |i|
   "ruby is cool!"
end

This is pretty easy to add to the Swift Int using an extension:

extension Int {
    func times(f: () -> () ) {
        for _ in 0..self {
            f()
        }
    }
}

10.times { "swift is cool too!" }

Note the _ instead of a variable in the for, because the value isn’t actually needed.

Next, two for alternatives, upto and downto:

1.upto(3) {|i| print "#{i}.. "} # prints 1.. 2.. 3..
3.downto(1) {|i| print "#{i}.. "} # prints 3.. 2.. 1..

in Swift would be:

extension Int {
    func upto(n: Int, f: (Int) -> () ) {
        for i in self...n {
            f(i)
        }
    }
    func downto(n: Int, f: (Int) -> () ) {
        for i in reverse(n...self) {
            f(i)
        }
    }
}

Note the use of the inclusive ... this time, unlike with times which used the convention of a zero base up to but not including n so needed non-inclusive .., because this time we want to start at self and count inclusively to n. Humorously, Ruby also has inclusive and exclusive ranges but .. and ... are the opposite way around.

For downto, the range is wrapped in a reverse in order to count backwards.

Next, some extensions to array, in a similar vein to map or reduce.

Ruby’s each is like map, but doesn’t generate any return value:

extension Array {
    func each(f: (Element) -> ()) {
        for e in self {
            f(e)
        }
    }
}

Element is a Type Property representing the type of value the Array contains, to this function works generically for type contained by array.

Ruby’s reverse_each does the same but in the opposite direction:

extension Array {
    func each(f: (Element) -> ()) {
        for e in Swift.reverse(self) {
            f(e)
        }
    }
}

Again, we use reverse to go backwards through the array. Wait, you might think, isn’t it inefficient to reverse the array just to iterate over it? But that’s not what reverse does – instead it generates a lazy collection that serves up the values in reverse order.

Note, we have to prefix it Swift.reverse to disambiguate it from the Array member function reverse – which would result in creating a whole new array in reversed order, if we used it.

Ruby’s delete_if is the opposite of Swift’s filter – it takes a discriminator function and returns any elements that don’t match. We could easily just implement it from scratch with a for loop, but instead let’s try and implement it by re-using filter.

One way to do this is to first create what’s called a “decorator”. Decorators are functions that take other functions, and return a new function that has changed the behaviour of the original function in some useful way.

What we want is a decorator that takes a function that returns a boolean, and then returns the opposite of that. Here it is:

// function that takes a function, f, that takes an element
// and returns a bool, and returns a function that applies f
// then returns the opposite
func not_f<T>(f: (T)->Bool) -> (T)->Bool {
    // this returns a closure that captures f
    return { !f($0) }
}

If you’re a bit hazy on closures and variable capture, read this.

Armed with not_f, we can define delete_if:

extension Array {
    func delete_if(f: (Element) -> Bool) -> Element[] {
        return self.filter(not_f(f))
    }
}

Finally, Ruby’s equivalent of filter is called select. It’s identical, it’s just called by a different name. Is there some way we could alias filter if we wanted?

Yup, like this:

extension Array {
    var select: ((Element) -> Bool) -> Element[] { 
        return Array.filter(self) 
    }
}

You can now use select in exactly the same way you use filter. This is quite a silly thing to do, but it does demonstrate a couple of language features: read-only computed properties that return closures, and references to member functions.

Read-only computed properties are used like regular properties i.e. can be accessed using the dot syntax, but behave like functions that take no arguments and return a value. In this case we have defined a property select that returns a function when you call it. We’re just returning an existing member function (more on that next) but you could have more complex logic that created and returned different kinds of closures.

The reason it’s nice to implement these as computed properties is you don’t need to use a () after the property name. This means if you want to compute a function for someone to use, they can use it like this: x.computedfun(). If computedfun was itself a function, you’d have to write this: x.computedfun()(), which looks odd. Other than that, they behave just like functions that return functions.

So what is select actually returning? To understand that, you need need to realize you can reference a classes’ member functions. See the following code:

class MyClass {
    let n: Int

    init(_ i: Int) { n = i }

    func multiply(i: Int) { 
        println("n: \(n) * i: \(i) = \(n*i)")
    }

    func add(i: Int) { 
        println("n: \(n) + i: \(i) = \(n*i)")
    }
}

let a = MyClass(2)
let b = MyClass(5)

// prints "n: 2 * i: 10 = 20"
a.multiply(10)

// prints "n: 5 + i: 10 = 50"
b.add(10)

// this takes a reference to the member 
// function multiply of MyClass
var memfunref = MyClass.multiply

// you can't use memfunref directly.
// you have to apply an instance of
// MyClass to it:
var instancefunref = memfunref(a)

// now you can call it, and it's
// like calling a.multiply, so
// this prints "n: 2 * i: 10 = 20" 
instancefunref(10)

// MyClass.add has the same type as
// MyClass.multiply, they're both (Int)->(),
// so you can assign it to memfunref too:
memfunref = MyClass.add

// and apply a different instance of MyClass
instancefunref = memfunref(b)

// this prints "n: 5 + i: 10 = 50"
instancefunref(10)

// or you can skip the instancefunref step
// prints "n: 5 + i: 10 = 50" again
memfunref(b)(10)

Now we can see what that computed property is doing. It’s returning the member function filter of Array, then applying self to it, and returning that. The caller then can call the returned function () and it runs filter against the object they fetched it from. Like I said, bit silly, but it demonstrates a feature that could probably be put to better use in other cases.

If you liked this post, this one is also about implementing Ruby features in Swift, in this case implementing the ||= operator using the @auto_closure Swift feature.

A Basic Tutorial on Functions and Closures in Swift

Posted on by airspeedvelocity

Note: this is an article for people new to functional programming style, and to closures. Unlike the rest of this blog, it is very much an explantion for beginners, so if you’re already familiar with these topics you might want to skip it.1 You may find these other articles interesting though – Implemeting an Accumulator in Swift, and A Straw-man Argument for Trying More Functional Programming in Swift.

If you like this post, consider buying a copy of our book, Advanced Swift, which includes introductory material like this, and then builds on it to cover many more advanced Swift topics.

Reading the /r/swift subreddit and stack overflow, there seems to be a lot of questions about functions and closures from programmers learning Swift. There’s confusion between what a closure is, what a function is, and what a closure expression is. And many people are new to the whole idea of functions being first class objects. This article is an attempt to help out.

To understand functions and closures in Swift you really need to understand three things, in roughly this order of importance:

  1. Functions can be assigned to variables and passed in and out of other functions as arguments, just as an Int or a String can be.
  2. Functions can “capture” variables that exist outside of their local scope.
  3. There are two ways of creating functions: with the func keyword, or with { }. Swift calls the latter “closure expressions”.

I suspect people new to the topic of closures are coming at it in reverse order, and maybe missing one of these points, or conflating the terms “closure” and “closure expression”, and that this can cause a lot of confusion. It’s a three-legged stool, and if you miss one of the three points above, you’ll fall over when you try to sit down.

1. Functions can be assigned to variables and passed in and out of other functions as arguments, just as an Int or a String can be.

In Swift, as in many modern languages, functions are referred to as “first-class objects”. You can assign functions to variables, and you can pass them in and out of other functions, to be called later.

This is the most important thing to understand. “Getting” this for functional programming is akin to “getting” pointers in C. If you don’t quite grasp this part, everything else will just be noise.

Here is an example of assigning functions to variables and passing them to functions:

// This is a function that takes an Int and prints it. 
func printInt(i: Int) {
    println("you passed \(i)")
}

// This assigns the function you just declared
// to a variable.  Note the absence of () after the 
// function name.
let funVar = printInt

// Now you can call that function using your variable. 
// Note the use of () after the variable name.
funVar(2)  // will print out "you passed 2" 

// You can also write a function that takes a
// function as an argument
func useFunction(funParam: (Int) -> () ) {
    // call the passed-in function:
    funParam(3)
}

// You can call this new function passing in either 
// the original function:
useFunction(printInt)
// or the variable
useFunction(funVar)

Why is being able to treat functions like this such a big deal? Because it allows you to easily write “higher-order” functions, which take functions as arguments and apply them in useful ways.

For example, arrays have a member function map that takes a function and applies it to each member of the array, returning a new array containing the results.

// a simple function that doubles an int
func doubler(i: Int) -> Int { return i * 2 }

// the following runs doubler on each number,
// returning a new array of the results
let a = [1, 2, 3, 4].map(doubler)

// a now contains [2, 4, 6, 8]

There are several other member functions in array that take functions – filter (takes a function that examines each element for inclusion in the returned array), sort (takes a function that determines a custom ordering for two elements), reduce (takes a function to incorporate each element in turn into a running value – e.g. plus to sum them, max to find the highest value element).

2. Functions can “capture” variables that exist in the context they were declared

You can also return functions from other functions:

// This is a function that returns another function.
// That other function takes an Int and returns nothing.
func returnFunc() -> (Int) -> () {
  func innerFunc(i: Int) {
    println("you passed \(i) to the returned func")
  }
  return innerFunc
}

let f = returnFunc()
f(3)  // will print "you passed 3 to the returned func"

(The funcName() ->(Int) ->() syntax can be a little confusing at first. Try not to get too hung up on it for now, come back to it in detail later when you understand more.)

If, when you declare a function, it references variables outside the function’s scope, those variables are “captured”, and stick around after they would otherwise fall out of scope and be destroyed.

To see this, let’s revisit our returnFunc function, but add a counter that increases each time we call it:

func returnFunc() -> (Int) -> () {
  var counter = 0  // local variable declaration
  func innerFunc(i: Int) {
    counter += i   // counter is "captured"
    println("running total is now \(counter)")
  }
  return innerFunc
  // normally counter, being a local variable, would  
  // go out of scope here and be destroyed. but instead, 
  // it will be kept alive for use by innerFunc
}

let f = returnFunc()
f(3)  // will print "running total is now 3"
f(4)  // will print "running total is now 7"

// if we call returnFunc() again, a fresh counter
// variable will be created and captured
let g = returnFunc()
g(2)  // will print "running total is now 2"
g(2)  // will print "running total is now 4"

// this does not effect our first function, which
// still has it's own captured version of counter
f(2)  // will print "running total is now 9"

Think of these functions combined with their captured variables as similar to instances of classes with a method (the function) and some member variables (the captured variables).

A combination of a function and an environment of captured variables is called a “closure” in computer programming terminology. So f and g above are examples of closures, because they capture and use a non-local variable (counter) that was declared outside them.

3. The { } syntax for closure expressions

In Swift, you can declare functions in two ways. One is with the func keyword demonstrated above. The other way is to use a “closure expression”.

Here is the doubler function from above, written using the closure expression syntax:

let doubler = { (i: Int) -> Int in return i*2 }
// doubler can be used just the same way as before
[1, 2, 3].map(doubler)

Functions declared as a closure expression can be thought of as function “literals”, in the same way as 1 and "hello" are Int and String literals. They are also anonymous – they aren’t named, unlike with the func keyword. The only way they can be used is if you assign them to a variable when they are created, as we do here with doubler.

The doubler declared using the closure expression, and the one declared earlier using the func keyword, are completely equivalent. They even exist in the same “namespace”, unlike in some languages i.e. if you declared doubler using func, and then doubler using let or var in the same scope, you’ll get an error that you are redeclaring something that has already been used (similar to if you tried to declare a variable with the same name twice).

Why is the { } syntax useful then? Why not just use func every time? Well, it can be a lot more compact, especially when writing quick functions to pass into other functions such as map. Here is our doubler map example written in a much shorter form:

[1, 2, 3].map { $0 * 2 }

This looks very different, because we’ve leveraged several features of Swift to compress it down. Here they are one by one:

  1. If you are passing the closure in as an argument, and that’s all you need it for, there’s no need to store it in a local variable first. Think of this like passing in a numeric expression, such as 5*i, to a function that takes an Int as a parameter.
  2. If all the types can be “inferred” from the context by the compiler, you don’t need to specify them. In this case, the function passed to map is taking in an Int (that’s what’s in the array), and returning an Int (because an Int times an Int is an Int), so we can leave the types off.
  3. If the closure expression is a single expression, you can leave off the return and it will automatically return the value of the expression.
  4. Swift automatically provides shorthand names for the arguments to the function – $0 for the first, $1 for the second etc.
  5. If the last argument to a function is a closure expression, you can move the expression outside the parenthesis of the function call. This is nice if you have a multi-line closure expression, as it more resembles a regular function definition, or other block statement such as if(expr) { }.
  6. Finally, if a function has no arguments other than a closure expression, you can leave off the parenthesis after the function name altogether.

Using each of the above rules, we can boil down the expression to the form above:

  1. [1, 2, 3].map( { (i: Int) ->Int in return i * 2 } )
  2. [1, 2, 3].map( { i in return i * 2 } )
  3. [1, 2, 3].map( { i in i * 2 } )
  4. [1, 2, 3].map( { $0 * 2 } )
  5. [1, 2, 3].map() { $0 * 2 }
  6. [1, 2, 3].map { $0 * 2 }

If you’re new to functional programming in general, and to Swift syntax, then these compact function declarations might seem daunting at first. But as you get more comfortable with the syntax, and with using functional programming style, they will start to feel more natural and you’ll be grateful for the ability to remove the clutter so you can see more clearly just what the code is doing. Once you get used to reading code written like this, it’ll be much clearer to you at a glance than code doing the same thing in a conventional for loop.

One final point on naming. It’s important to remember that functions declared with func can be closures, just like ones declared with { }. Remember, a closure is a function combined with any captured variables. While functinos created with { } are called “closure expressions”, people often refer to this syntax as just “closures”. But don’t get confused and think that functions declared with the closure expression syntax are different from other functions – they aren’t.2 They are both functions, and they can both be closures.

Once you think you understand everything in this article, try reading some more advanced articles that involve closures on this blog – Implemeting an Accumulator in Swift, and Implementing Ruby’s ||= in Swift.

  1. Or read it for the purpose of giving me nitpicking feedback, which would be great. ↩
  2. Well, OK, they are. For example you can’t do the skipping the return statement trick with a one-line func. But that’s just syntactic sugar, the point is they don’t differ in the fundamental way they behave. ↩