Fixed-length Sequences in Swift 2.2

Question

The following is an implementation of fixed-length sequences that makes very exotic (and hopefully fun) use of Swift 2.2 types. The question is what exactly is the cost of having the type checker guaranteeing sequence length in this way on safety? performance? readability?

protocol CountType {
    static var count: Int { get }
}

protocol DigitType : CountType {}

enum _0 : DigitType { static let count = 0 }
enum _1 : DigitType { static let count = 1 }
enum _2 : DigitType { static let count = 2 }
enum _3 : DigitType { static let count = 3 }
enum _4 : DigitType { static let count = 4 }
enum _5 : DigitType { static let count = 5 }
enum _6 : DigitType { static let count = 6 }
enum _7 : DigitType { static let count = 7 }
enum _8 : DigitType { static let count = 8 }
enum _9 : DigitType { static let count = 9 }

At this point we can do very little:

_4.count // 4
_2.count // 2

To express larger natural numbers, however, we must combine DigitTypes:

import CoreGraphics // TODO: wean off (implement `pow`)

extension DigitType {
    static func value(place place: Int) -> Int {
        return count * Int(pow(10, CGFloat(place)))
    }
}

enum __<T:DigitType, U:DigitType> : CountType { // these are two underscores `_`x2 (then, below, three, four...)
    static var count: Int {
        return T.value(place: 1) + U.value(place: 0)
    }
}
enum ___<H:DigitType, T:DigitType, U:DigitType> : CountType {
    static var count: Int {
        return H.value(place: 2) + T.value(place: 1) + U.value(place: 0)
    }
}
enum ____<Th:DigitType, H:DigitType, T:DigitType, U:DigitType> : CountType {
    static var count: Int {
        return Th.value(place: 3) + H.value(place: 2) + T.value(place: 1) + U.value(place: 0)
    }
}

... which allows us to count in types (try it in the playground):

____<_2,_0,_1,_6>.count // 2016

The point is that we can now make use of CountTypes to define sequence length:

final class Box<T> {
    var value: T
    init(_ value: T) { self.value = value }
}

struct Vector<Dimension: CountType, Element> : SequenceType {

    private let array: [Box<Element>]
    var elements: [Element] { return array.map{ $0.value } }

    subscript(index: Int) -> Box<Element> { return array[index] }

    init(_ repeatedValue: Element) {
        array = (0..<Dimension.count).map{ _ in Box(repeatedValue) }
    }

    func generate() -> Array<Element>.Generator {
        return elements.generate()
    }
}

// TODO: Matrix<Rows: CountType, Cols: CountType, Element>

We may now work with such Vectors and Matrixes with confidence that their dimension can never change:

let v = Vector<__<_4,_2>,Int>(0)
v.elements.count // 42

let w = Vector<_3,Int>(0)
w.elements // [0, 0, 0]
w[2].value = 5

for x in w {
    x // 0, 0, 5
}

(hm... the underscore syntax looks prettier in my playground...)

I was considering various alternative naming schemes for the combining enums. So, instead of underscores, we could perhaps emulate the exponent syntax for number literals (like 0.42e2 meaning 0.42 * pow(10, 2)). This would work out as following:

e4<_2,_0,_1,_6>.count // 2016

// and

let v = Vector<e2<_4,_2>,Int>(0)

The reason I decided against this and similar approaches is that there is now a rather irrelevant number 2 appearing alongside _4,_2...

Answer 1

The Vector type is not related to graphics, so importing CoreGraphics seems "unnatural" here. If you replace CGFloat by Float or Double

extension DigitType {
    static func value(place place: Int) -> Int {
        return count * Int(pow(10, Double(place)))
    }
}

then it suffices to import Foundation (or Swift + Darwin).

But I would get rid of the floating point conversion and implement it as (taking the hundreds as an example):

enum ___<H: DigitType, T: DigitType, U: DigitType> : CountType {
    static var count: Int {
        return H.count * 100 + T.count * 10  + U.count
    }
}

This is simple and straightforward, and easy to read. This makes the value(place place:) with its floating point conversion, and the the math library call to the pow() function obsolete.

As a consequence, the entire code compiles with a pure

import Swift

without additional imports.

---

(This is my major point.) The boxing of the array elements into a class seems problematic to me.

First, struct Vector is a value type, but its elements are mutable even for a constant:

let vecA = Vector<_3, Int>(0)
vecA[0].value = 111 // This should not compile!

Second, copying a vector copies references to the elements, which is not to be expected for a value type:

let vecA = Vector<_3, Int>(0)
vecA[0].value = 111

let vecB = vecA
vecB[0].value = 222

print(vecA[0].value) // Output: 222. Expected output: 111.

Here, modifying the elements of vecB modifies the elements of vecA as well.

I would simply omit the boxing and store the elements just as an array. Modifying the elements is then done via a subscript setter:

struct Vector<Dimension: CountType, Element> {

    private var array: [Element]

    init(_ repeatedValue: Element) {
        array = [Element](count: Dimension.count, repeatedValue: repeatedValue)
    }

    var elements: [Element] {
        return array
    }

    subscript(index: Int) -> Element {
        get {
            return array[index]
        }
        set(newValue) {
            array[index] = newValue
        }
    }

    func generate() -> Array<Element>.Generator {
        return array.generate()
    }
}

Using a private var array for the element storage and a computed elements property still makes sense for encapsulation.

Now Vector behaves like a proper value type:

var vecA = Vector<_3, Int>(0)
vecA[0] = 111

var vecB = vecA
vecB[0] = 222

print(vecA[0]) // Output: 111

---

By adopting the CustomStringConvertible protocol,

extension Vector : CustomStringConvertible {
    var description: String {
        return "<" + (array.map { String($0) }).joinWithSeparator(", ") + ">"
    }
}

printing a vector produces nicer output (the angle brackets are just an example to disambiguate the output from an array):

print(vecA)
// Output: <111, 0, 0>
// instead of Vector<_3, Int>(array: [111, 0, 0])

---

To create (constant) vectors, an init method taking a "index to element mapping" might be useful:

extension Vector {
    init(elementForIndex: Int -> Element) {
        array = (0 ..< Dimension.count).map(elementForIndex)
    }
}

Example:

let vecC = Vector<_5, Int>(elementForIndex: { 2 * $0 })
print(vecC) // <0, 2, 4, 6, 8>

This would also come in handy when you start to define operations on the vector type, e.g. an addition of integer vectors:

func + <Dimension, Element: IntegerArithmeticType>
    (lhs: Vector<Dimension, Element>, rhs: Vector<Dimension, Element>)
    -> Vector<Dimension, Element> {
        return Vector(elementForIndex: { lhs[$0] + rhs[$0]})
}

---

Initialization from an array or array literal might also be convenient:

extension Vector {
    init(elements: [Element]) {
        precondition(elements.count == Dimension.count)
        array = elements
    }
}

extension Vector: ArrayLiteralConvertible {
    init(arrayLiteral elements: Element...) {
        self.init(elements: elements)
    }
}

Example:

let vecD: Vector<_5, Double> = [ 1.0, 2.0, 3.0, 4.0, 5.0 ]
print(vecD) // <1.0, 2.0, 3.0, 4.0, 5.0>

The disadvantage here is that the compiler cannot check the dimension.