## Monty Hall

The Monty Hall problem is a great example of how counter-intuitive probability can sometimes be. It goes something like this: say you’re on a gameshow, with the chance to win a car. You’re shown three doors, and the car is behind one, goats behind the other two. You pick a door, say the leftmost, but then the host of the gameshow stops you before it’s opened. He opens one of the two doors you didn’t pick, revealing a goat. He then asks you if you’d like to change your decision. So? Do you?

## Yet More Misunderstanding of Dependent Types

Dependent types are types “that depend on values”. Say you had a function `f` that took an integer. If you can write that function whereby it returns a value of type `A` when that integer is even, or a type `B` if the integer is odd, then you’re working with dependent types. (I think. I’m not sure: if I’ve gotten it wrong tweet me.)

## In which I Misunderstand Dependent Types

All of this available as a shiny, fancy playground here.

So there was a blog post the other day about dependent types:

Why Dependent Types Matter

Most blog posts that deal with the more mathematical/category theory side of programming go over my head when I read them, only to become suddenly clear a few weeks down the line. I have not reached this such sudden clarity with this post, but I’m starting to see a glimmer.

## Using Protocols to Build a (very) Generic Deque

Check out this blog post as a cool fancy markdown-tastic playground here. Look! It’s the future!

This post is an update on a previous implementation of a Deque. A full implementation of this Deque is available here.

A Deque is a data structure comprised of two stacks, facing opposite directions. In this way, operations at either end of the Deque have the same complexity as operations on one end of the underlying stack. This implementation uses two arrays, with the front reversed: appending, prepending, and removal of the first and last elements are all (amortized) O(1).

The standard library has three Array structs: `Array`, `ArraySlice`, and `ContiguousArray`. They all have the same interface, with different underlying implementations. An `Array` is a standard vector-like structure, which allows O(1) amortized appending, fast iteration, etc. A `ContiguousArray` has stricter rules about contiguity, but it’s not bridged to Objective-C.

```let cArray: ContiguousArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```

An `ArraySlice` is a reference into an `Array` or `ContiguousArray`, for more efficient slicing. All the information an `ArraySlice` contains is the beginning and end points of the slice (as well as any changes made to the slice separate from the array)

```let slice = array[0..<6]
```

To replicate these semantics in a Deque requires three separate structs: one with an `Array` as the stack, another with an `ArraySlice` as the stack, and a third with a `ContiguousArray`. The standard library seems to duplicate the structs, along with their methods and properties.

It would be much nicer to just define a protocol that represented the difference between the deque types: then you could just write the methods and properties once, on top of it. Something like this:

```protocol DequeType {
typealias Container : RangeReplaceableCollectionType, MutableSliceable
var front: Container { get set }
var back : Container { get set }
init()
}
```

There’s one problem with this: both stacks need to be made public. It would be much nicer to hide the stacks (especially since an invariant needs to be checked and maintained on every mutation). If anyone has an idea of how to transformations that, tweet me.

The first method to implement is a subscript. Indexing is difficult, because the front stack will be reversed, so the index used to get in to the Deque will need to be translated into an equivalent index in the array.

Any (valid) index will point into either the front or back queue, and the transformation applied to it in each case is different. If it’s in the front, the end result will look like `front[front.endIndex - 1 - i]`, whereas if it’s in the back, it should be `back[i - front.endIndex]`. There’s nothing specified about the Containers except that they’re `RangeReplaceableCollectionType` and `MutableSliceable`, so the index types will have to be as generic as possible. (you could specify `where Index == Int`, but that’s more specific than needed, and not very extensible.)

Both of those transformations are subtractions, an operation that’s possible on `RandomAccessIndexTypes` with the `advancedBy` method. `advancedBy` takes the associated `Distance` type of the `RandomAccessIndexType`. That’s enough information to figure out that the Deque’s index type must be the same as the Distance of the Index of the Container.

```extension DequeType {
typealias Index = Container.Index.Distance
}
```

The method that will translate an index into the relevant index in the stacks will return an enum:

```public enum IndexLocation<I> {
case Front(I), Back(I)
}
```

Then, the translate method itself:

```extension DequeType where
Container.Index : RandomAccessIndexType,
Container.Index.Distance : ForwardIndexType {

private func translate(i: Container.Index.Distance)
-> IndexLocation<Container.Index> {
return i < front.count ?
}
}
```

This performs two steps:
1. Check which stack it’s in.
2. Subtract in the appropriate order

```let d: Deque = [1, 2, 3, 4, 5, 6] // [1, 2, 3 | 4, 5, 6]

d.translate(0) // Front: 2
d.translate(4) // Back: 1
```

This means that the logic for converting distance to index is separated from the logic for actual indexing. Great! Here’s the indexing:

```extension DequeType where
Container.Index : RandomAccessIndexType,
Container.Index.Distance : ForwardIndexType {
var startIndex: Container.Index.Distance { return 0 }
var endIndex  : Container.Index.Distance { return front.count + back.count }
subscript(i: Container.Index.Distance) -> Container.Generator.Element {
get {
switch translate(i) {
case let .Front(i): return front[i]
case let .Back(i): return back[i]
}
} set {
switch translate(i) {
case let .Front(i): front[i] = newValue
case let .Back(i): back[i] = newValue
}
}
}
}
```

This makes things much easier to test and debug.

Here’s where the power of protocols becomes obvious. If you go back to the original definition of `DequeType`, you can add `Indexable`. It may seem like now only indexable things can conform, but what happens in practice is that when `Indexable` looks for its requirements, it can use the implementations in DequeType. That means that we’ve just made anything that can conform to `DequeType` indexable. That’s awesome.

Next job is ranged indices. This is a good bit more complicated than the individual indices, so it definitely will benefit from being separated into a translate method:

```extension DequeType where
Container.Index : RandomAccessIndexType,
Container.Index.Distance : BidirectionalIndexType {

private func translate
(i: Range<Container.Index.Distance>)
-> IndexRangeLocation<Container.Index> {
if i.endIndex <= front.count {
if s == front.startIndex && i.isEmpty { return .Between }
return .Front(s..<e)
}
if i.startIndex >= front.count {
let s = back.startIndex.advancedBy(i.startIndex - front.count)
let e = back.startIndex.advancedBy(i.endIndex - front.count)
return .Back(s..<e)
}
let b = back.startIndex..<back.startIndex.advancedBy(i.endIndex - front.count)
return .Over(f, b)
}
}

let otherDeque: Deque = [0, 1, 2, 3, 4, 5] // [0, 1, 2 | 3, 4, 5]

otherDeque.translate(0...2) // Front: 0..<3
otherDeque.translate(4...5) // Back: 1..<3
otherDeque.translate(2...5) // Over: 0..<1, 0..<3
otherDeque.translate(3..<3) // Between
```

The invariant that must be maintained in the deque is this: if either stack has more than one element, the other cannot be empty. If the invariant is violated, the longer stack is reversed, and put in place of the shorter.

```public enum Balance {
case FrontEmpty, BackEmpty, Balanced
}

extension DequeType {

public var balance: Balance {
let (f, b) = (front.count, back.count)
if f == 0 {
if b > 1 {
return .FrontEmpty
}
} else if b == 0 {
if f > 1 {
return .BackEmpty
}
}
return .Balanced
}

public var isBalanced: Bool {
return balance == .Balanced
}
}
```

A deque is a good data structure for certain uses, especially those that require popping and appending from either end. `popFirst()` and `popLast()` aren’t included in the standard `RangeReplaceableCollectionType`, though, so we’ll have to add our own.

```extension RangeReplaceableCollectionType where Index : BidirectionalIndexType {
private mutating func popLast() -> Generator.Element? {
return isEmpty ? nil : removeLast()
}
}

var mutableDeque: Deque = [0, 1, 2, 3, 4, 5]
mutableDeque.popLast() // 5
mutableDeque           // [0, 1, 2 | 3, 4]

extension DequeType where Container.Index : BidirectionalIndexType {
public mutating func popLast() -> Container.Generator.Element? {
return back.popLast()
}
}
```

The method needs to include `check()`, which we can do with `defer`:

```mutating func popLast() -> Container.Generator.Element? {
defer { check() }
return back.popLast()
}

mutableDeque.popLast() // 4
mutableDeque           // [0, 1, 2 | 3]
mutableDeque.popLast() // 3
mutableDeque           // [0 | 1, 2]
```

You also can’t just pop from the back queue in `popLast()`, because it may be the case that the front stack has one element left

```//mutating func popLast() -> Container.Generator.Element? {
//  defer { check() }
//  return back.popLast() ?? front.popLast()
//}

mutableDeque.popLast() // 2
mutableDeque.popLast() // 1
mutableDeque           // [0|]
mutableDeque.popLast() // 0
mutableDeque           // [|]
mutableDeque.popLast() // nil
```

The rest of the Deque was easy, with little to no repetition. Using protocols in this way was really surprisingly powerful: now, you can define a `DequeType`, with full access to all of the collection methods, all the way up to `RangeReplaceableCollectionType`, in five lines:

```public struct Deque<Element> : DequeType {
public var front, back: [Element]
public typealias SubSequence = DequeSlice<Element>
public init() { (front, back) = ([], []) }
}

public struct DequeSlice<Element> : DequeType {
public var front, back: ArraySlice<Element>
public typealias SubSequence = DequeSlice
public init() { (front, back) = ([], []) }
}
```

There’s no performance hit, there’s no safety problems. I only have one version of code to test, one version to change, one version to read. It’s completely extensible: you could use any kind of stack for the front and back. Even another Deque, if you were so inclined:

```struct DequeDeque<Element> : DequeType {
var front, back: Deque<Element>
typealias SubSequence = DequeDequeSlice<Element>
init() { front = Deque(); back = Deque() }
}

struct DequeDequeSlice<Element> : DequeType {
var front, back: DequeSlice<Element>
typealias SubSequence = DequeDequeSlice
init() { front = DequeSlice(); back = DequeSlice() }
}

let dd: DequeDeque = [1, 2, 3, 4, 5, 6, 7, 8]
dd.front // [4 | 3, 2, 1]
dd.back  // [5 | 6, 7, 8]
```

Woo protocols!

## Using Higher-Order Methods Everywhere

Filter is one of the higher-order sequence methods in Swift that can be used and abused in surprising ways. Using it for what it’s not intended for can really drag on your efficiency, though. Say you want to find the first element of a sequence that matches some predicate:

```someSequence.filter(somePredicate).first
```

## Sequence Conformance

So you want to conform to `SequenceType`. Maybe you’re even more ambitious than that: `CollectionType`, `MutableSliceable`, `RangeReplaceableCollectionType` – you want it all. What’s involved?

## Stasis

So this static typing thing. Statically-dispatched protocols, all that. Why are they the way they are? Why do we bother? What are the pros and cons?

## A Trie in Swift

By Slaunger (Own work) CC BY-SA 4.0

(all code from this post available here)

If you google “cool data structures” you’ll get this as your first result. It’s a stackoverflow question: “What are the lesser known but useful data structures?”. And the top answer is a Trie. I read up on them, and found out a lot of cool things about their use (as well as finding out that I’m now the kind of person who googles “cool data structures”). So I rocked on up to my playground, and got writing.

## Yet Another Root of All Evil

(All the code from this post is available here)

So I watched this video the other day:

It’s a great lecture. I’d recommend the whole thing. The main thrust of the talk is a theme that I’ve always had a little trouble with: performance. Performance is an odd topic in computer science: for something so obviously empirical, there’s an awful lot of (seeming) mysticism around some of the concepts. For beginners like me, it makes performance seem like an untouchable, too-difficult-for-you area.

## It’s Not (All) About the Speed

Swift is a young language. We still don’t really know what it’s all about. And while the reception has generally been pretty good, many devs have been hesitant to use it. A lot of the time it’s for mundane reasons: too much Objective-C to convert (right now), current release not stable enough, not widely available for other platforms. Other times, though, the language itself will be criticised. Some of these criticisms are aimed at the implementation: bugs in Xcode, gaps in the standard library, that sort of thing. But what I’m interested in are the criticisms of the design of Swift.