Archive for the ‘Tim’ Category

Working with text output streams

Here’s another great write-up from Tim V. 

By far the most common way to add a custom textual representation to a type is by implementing CustomStringConvertible. Consider this type:

struct Person {
    let name: String
    let age: Int
    let spouse: String?
    let children: [String]
}

A pretty standard way to conform to CustomStringConvertible would be this:

extension Person: CustomStringConvertible {
    var description: String {
        var description = ""
        
        description += "Name: \(name)\n"
        description += "Age: \(age)\n"
        
        if let spouse = spouse {
            description += "Spouse: \(spouse)\n"
        }
        
        if !children.isEmpty {
            description += "Children: \(children.joined(separator: ", "))\n"
        }
        
        return description
    }
}

This code doesn’t look too bad, but it’s a pain to write var description = "" and return description over and over, if this is a pattern you commonly use. It’s also quite easy to forget to add \n to each line.

The relatively unknown standard library protocol TextOutputStreamable solves both of these problems for you. Rather than adding a description computed property, all you have to do is write your properties to a TextOutputStream instance:

extension Person: TextOutputStreamable {
    func write<Target: TextOutputStream>(to target: inout Target) {
        print("Name:", name, to: &target)
        print("Age:", age, to: &target)
        
        if let spouse = spouse {
            print("Spouse:", spouse, to: &target)
        }
        
        if !children.isEmpty {
            print("Children:", children.joined(separator: ", "), to: &target)
        }
    }
}

That’s it! Whenever something that conforms to TextOutputStreamable but not to CustomStringConvertible is turned into a string, the write(to:) method we just implemented is used:

let person = Person(name: "Michael", age: 45, spouse: "Emma", children: ["Charlotte", "Jacob"])
print(person)

>Name: Michael
>Age: 45
>Spouse: Emma
>Children: Charlotte, Jacob

If you enjoyed this write-up, you might be interested in an old post I wrote about using streams to transform data.

Writing a binary search tree

Tim discusses using Swift enumeration indirect keywords to build binary tree nodes. Read on to learn more about how reference types and value semantics combine…

Today we’re writing a simple binary search tree in Swift. While binary search trees seem to be very powerful in theory, their performance is rather disappointing in practice. Other, more advanced tree-shaped data structures such as red-black trees and B-trees solve some of the practical problems that binary search trees have, and are subsequently much more useful in performance-critical code. Nevertheless, learning about binary search trees is the first step to getting more familiar with this class of data structures.

Probably the simplest way to represent a binary tree in Swift is by using an indirect enum, like so:

enum BinarySearchTree<Element: Comparable> {
    case empty
    indirect case node(left: BinarySearchTree, value: Element, right: BinarySearchTree)
}

While indirect enums use reference types under the hood, they have value semantics by default. So that’s nice.

From all the standard library’s protocols, SetAlgebra and BidirectionalCollection both seem a good fit for our BinarySearchTree type: SetAlgebra for inserting and removing elements, and BidirectionalCollection for traversing the tree (both forwards and backwards, hence the name). However, for the purpose of this post, we’ll stick to only a couple basic methods.

Let’s start with insertion. Because of the way enums with associated values work, it’s easiest to implement the insert method using an under-the-hood inserting method:

extension BinarySearchTree {
    mutating func insert(_ element: Element) {
        self = inserting(element)
    }
    
    private func inserting(_ element: Element) -> BinarySearchTree {
        switch self {
        case .empty:
            // the tree is empty, so inserting an element results in a tree containing only that element
            return .node(.empty, element, .empty)
            
        case .node(_, element, _):
            // the element is already present in the tree
            return self
            
        case let .node(left, value, right) where element < value:
            // the element should be inserted into the left subtree
            return .node(left.inserting(element), value, right)
            
        case let .node(left, value, right):
            // the element should be inserted into the right subtree
            return .node(left, value, right.inserting(element))
        }
    }
}

Now we can insert values into a tree, but we can’t read them in any way. So let’s add a contains method as well:

extension BinarySearchTree {
    func contains(_ element: Element) -> Bool {
        switch self {
        case .empty:
            // an empty tree obviously doesn't contain any elements!
            return false
            
        case .node(_, element, _):
            // the element is equal to this node's value
            return true
            
        case let .node(left, value, _) where element < value:
            // if the element is present in the tree, it must be in the left subtree
            return left.contains(element)
            
        case let .node(_, _, right):
            // if the element is present in the tree, it must be in the right subtree
            return right.contains(element)
        }
    }
}

Let’s try it out!

var tree = BinarySearchTree.empty

tree.contains(5) // => false
tree.insert(5)
tree.contains(5) // => true
tree.insert(3)
tree.contains(3) // => true
tree.contains(5) // => true

Looks good. We can’t actually remove elements, though, but that is a real pain to implement and it’s out of scope for this post.

Finally, to iterate over a binary search tree, we need to implement the IteratorProtocol protocol. We’ll use an in-order traversal algorithm:

extension BinarySearchTree: Sequence {
    func makeIterator() -> BinarySearchTreeIterator<Element> {
        return BinarySearchTreeIterator(self)
    }
}

struct BinarySearchTreeIterator<Element: Comparable>: IteratorProtocol {
    var node: BinarySearchTree
    var stack: [(Element, BinarySearchTree)] = []
    
    init(_ node: BinarySearchTree) {
        self.node = node
    }
    
    public mutating func next() -> Element? {
        while case let .node(left, value, right) = node {
            stack.append((value, right))
            node = left
        }
        
        guard let (element, node) = stack.popLast() else { return nil }
        
        self.node = node
        return element
    }
}

Now we can do all kinds of sequence-y stuff with trees, like so:

var tree = BinarySearchTree.empty
[5, 2, 4, 8, 3, 2].forEach { tree.insert($0) }

for element in tree {
    print(element, terminator: " ") // => 2 3 4 5 8
}

tree.reduce(0, +)                                  // => 22
tree.lazy.map(String.init).joined(separator: ", ") // => 2, 3, 4, 5, 8

And the list goes on.

That’s it for now! If you enjoy this kind of stuff, make sure to check out Károly Lőrentey’s brand new book Optimizing Collections in which he in much detail goes through implementing several data structures in Swift, focusing on performance. As of writing this post, it’s 25% off.

Using memory addresses for hashing

Today, Tim talks about conforming reference types to a hashable program. This enables you to use specific class instances for set elements and dictionary keys. Read on to learn more and don’t forget to follow Tim on Twitter.

For reference types, it often makes sense to consider two variables to be equal when they reference the same address in memory. Say you have a UIView instance visible on screen, for example. You could create a copy of that view with the exact same properties (size, position, background color, etc.) but modifying the copy will obviously have no visible effect.

Testing whether two variables refer to the same instance is easy using the identity operators (=== and !==). However, this does not allow you to put instances of an arbitrary class in a Set, or use them as keys in a Dictionary, since that requires conforming to the Hashable protocol.

Interestingly, classes that inherit from NSObject don’t face this problem: NSObject implements == and hashValue, the two requirements of the Hashable protocol, using isEqual(_:) and hash respectively. The default implementation of isEqual uses pointer equality, and the default value for hash is the instance’s memory address.

In order to use memory addresses for hashing without inheriting from NSObject (which you shouldn’t), you can use the ObjectIdentifier type that is part of the Swift standard library:

final class Foo: Hashable {
    static func == (left: Foo, right: Foo) -> Bool {
        return left === right
    }
    
    var hashValue: Int {
        return ObjectIdentifier(self).hashValue
    }
}

Note that an instance’s memory address can (and will) change across different executions of the program, but that’s fine: the Hashable protocol doesn’t require hash values to be stable across different executions.

Of course, you can put this code in a protocol extension to make it reusable:

protocol PointerHashable: class, Hashable {}

extension PointerHashable {
    static func == (left: Self, right: Self) -> Bool {
        return left === right
    }
    
    var hashValue: Int {
        return ObjectIdentifier(self).hashValue
    }
}

Now, all it takes for a custom class to be usable as set elements and dictionary keys is conformance to PointerHashable. But be careful: the Hashable protocol requires that two instances that are considered equal with == also have the same hash value, so if you are implementing == using custom logic, you will need a custom hashValue implementation as well.

Tests that don’t crash

Give a big hi to Tim V! He’ll be posting here when a topic inspires him and today, he’s going to talk about how to write tests that fail gracefully.

Most people that have been writing Swift code for a while try to limit their usage of optional force unwraps and try! as much as possible. Test code, on the other hand, is often still littered with unsafe code. It’s true that crashes in tests aren’t nearly as undesirable as in production code, but it’s fairly straight-forward to write tests that fail gracefully when an unexpected nil is encountered, or when an error is thrown unexpectedly.

Consider the following unit tests:

class Tests: XCTestCase {
    func testFoo() {
        let value = try! foo()
        XCTAssertEqual(value, 5)
    }
    
    func testBar() {
        let value = bar()!
        XCTAssertEqual(value, "bar")
    }
}

What a lot of people don’t seem to know is that individual tests can be marked with throws to automatically handle thrown errors:

func testFoo() throws {
    let value = try foo()
    XCTAssertEqual(value, 5)
}

Much better. To write testBar in a safer way, we’ll need to throw an error when the output of bar is nil. We could declare a separate error for each optional value we want to unwrap in one of our tests, but that requires writing a lot of extra code. Instead, we can throw a more general Optional.Error.unexpectedNil each time an unexpected nil value is encountered:

extension Optional {
    enum Error: Swift.Error {
        case unexpectedNil
    }
    
    func unwrap() throws -> Wrapped {
        guard let value = self else { throw Error.unexpectedNil }
        return value
    }
}

Note: Swift 3.0 and below does not support nesting types inside a generic type, so if you’re not yet using Swift 3.1, you’ll have to declare a separate enum OptionalError instead.

Now we can rewrite testBar as follows:

func testBar() throws {
    let value = try bar().unwrap()
    XCTAssertEqual(value, "bar")
}

After these changes, whenever a test would normally crash, it now simply fails. And as a bonus, all tests are guaranteed to be executed, where previously a single crash would prevent the remaining tests from being run.