Indirect Enums

Credits to the great wonderful amazing Daniel Vebman for introducing me to the topic

Indirect Enums are the most functional of types. For this entry, I will be assuming you have already or are currently taking 3110. Let's get into things!

Ever wanted to make natural numbers in Swift? Neither have I, but here's how to do it. As a quick refresher, here's the OCaml version:

type Nat = 
| Zero
| Succ of Nat

Hopefully, this rings a bell. 3 would be Succ (Succ (Succ Zero)).

In Swift, ideally you could do:

enum Nat {
    case zero
    case succ(Nat)
}

Sadly, this does not compile: "Recursive enum 'Nat' is not marked 'indirect'".

A little look into what's going on here: types like enums and structs require that memory size is known at compile time. With recursion, it has no clue what the size is. As it suggests, we can use the keyword indirect to circumvent this:

enum Nat {
    case zero
    indirect case succ(Nat)
}

indirect enum Nat {
    case zero
    case succ(Nat)
}

Both of the above Nat's are valid. Making an entire enum indirect makes all of the cases indirect, but you can also make individual cases indirect. Alright, well let's start building this thing out!

First, let's create some functions to help us create and analyze Nats:

var value: Int {
    get {
        switch self {
            case .zero: return 0
            case let .succ(sub): return 1 + sub.count
        }
    }
}

static func fromInt(_ int: Int) -> Nat {
    assert(int >= 0)
    if int == 0 {
        return .zero
    } else {
        return .succ(fromInt(int - 1))
    }
} 

Time to test!

for i in 0...100 {
    assert(i == Nat.fromInt(i).count)
}
// And one more
let x: Nat = .succ(.succ(.succ(.zero)))
assert(x.count == 3)

Great those passed! Let's work on adding some operators. I'll start off with an important one for code: ++ that Swift happens to lack:

static postfix func ++ (lhs: inout Nat) {
    lhs = .succ(lhs)
}

Now, this is some dang cool Swift! We're really cooking :) Let's test before we get ahead of ourselves:

var x = Nat.fromInt(3)
x++
x.count
// 4: Int

I'll stop babying you for the rest. Try it out! Have some fun!

I implemented +, -, and *.

Here's my code:

indirect enum Nat {
    case zero
    case succ(Nat)

    static postfix func ++ (lhs: inout Nat) {
        lhs = .succ(lhs)
    }

    var count: Int {
        get {
            switch self {
            case .zero: return 0
            case let .succ(sub): return 1 + sub.count
            }
        }
    }

    static func + (_ lhs: Nat, _ rhs: Nat) -> Nat {
        switch lhs {
        case .zero: return rhs
        case let .succ(sub): return sub + .succ(rhs)
        }
    }

    static func - (_ lhs: Nat, _ rhs: Nat) -> Nat {
        switch (lhs, rhs) {
        case (.zero, _), (_, .zero): return lhs
        case let (.succ(sub), .succ(remaining)): return sub - remaining
        }
    }

    static func * (_ lhs: Nat, _ rhs: Nat) -> Nat {
        switch lhs {
        case .zero: return .zero
        case let .succ(sub): return (sub * rhs) + rhs
        }
    }

    static func fromInt(_ int: Int) -> Nat {
        assert(int >= 0)
        if int == 0 {
            return .zero
        } else {
            return .succ(fromInt(int - 1))
        }
    }
}

// Construction Tests
for i in 0...100 {
    assert(i == Nat.fromInt(i).count)
}
// And one more
let x: Nat = .succ(.succ(.succ(.Zero)))
assert(x.count == 3)

// Random tests
for _ in 0...100 {
    let a = Int.random(in: 0...10)
    let b = Int.random(in: 0...10)
    let A = Nat.fromInt(a)
    let B = Nat.fromInt(b)
    assert(a + b == (A + B).count)
    assert(max(a - b, 0) == (A - B).count)
    assert(a * b == (A * B).count)
}

print("done")