毎月おなじみの関西モバイルアプリ研究会で「Swiftで自然数を作るっ」という発表でライブコーディングをしました．

<a href="http://kanmoba.connpass.com/event/18762/">関西モバイルアプリ研究会 #5 (2015/08/26 19:30〜)</a>kanmoba.connpass.com

書いたコードはgistで公開しています(少し長いので最後に埋め込んであります)．

自然数についてはWikipediaの項目を参照してください．

コードだけだとわかりにくいとおもうので少し解説を書きます．

解説コーナー

自然数のデータ構造を作る

例えば，自然数3は以下のように表現できます．

suc(suc(suc(0)))

要は0からはじめて3回後に進んだ状態です．この構造をSwiftで表現すると，

enum N {
    case Zero
    indirect case Succ(N)
    
    static func succ(n: N) -> N {
        return .Succ(n)
    }
}

となります． Swift2で新たに追加されたindirectによって再帰的なenumが作れるようになったので，このような表現が可能です．ちなみに，.Sucでなく.Succにしているのは.Zeroと揃えるためです．

static func succ(n: N) -> N はある自然数の次の自然数を得るための関数です． mutatingは絶対書きたくないので普通の関数にしています．

.Succ(.Succ(.Succ(...))) のようにネストしまくればどんな数でも作れるようになりましたが，さすがに10みたいな値を作るのは難しいのでヘルパ用意します．

extension N {
    init(from: UInt) {
        self = Repeat(count: Int(from), repeatedValue: N.succ).reduce(.Zero) { $1($0) }
    }
}

負の値が入力されるとinit?にする必要があって面倒なので，ズルしてfrom: UIntにします． fromの回数ぶん.Succで囲えばいいので，長さfromで中身が全部N.succの配列を用意して，.Zeroに当てはめます．要はこれと同じです．

var n: N = .Zero
for (var i = 0; i < from; i++) {
  n = N.succ(n)
}
self = n

同値，順序

これだけだと正しく実装できているのか証明できないので同値と順序を実装します． SwiftではEquatableとComparableプロトコルがそれに当たりますね．最低Equatableではfunc ==(_:_:) -> Boolを，Comparableではfunc <(_:_:) -> Boolを実装する必要があります． (これだけで==，!=，<，<=，>，>=が使えるようになります)

extension N: Equatable, Comparable {}

func ==(lhs: N, rhs: N) -> Bool {
    switch (lhs, rhs) {
    case (.Zero, .Zero): return true
    case let (.Succ(a), .Succ(b)): return a == b
    default: return false
    }
}

func <(lhs: N, rhs: N) -> Bool {
    switch (lhs, rhs) {
    case (.Zero, .Succ(_)): return true
    case let (.Succ(a), .Succ(b)): return a < b
    default: return false
    }
}

==は両辺共に.Zeroなら真，共に.Succなら中の値で再帰，それ以外は偽です． <も同様で，左辺が.Zeroで右辺が.Succなら真，両辺共に.Succなら中の値で再帰，それ以外は偽です．単純なパターンマッチで実装できますね．

加法・乗法

定義に従って，

func +(lhs: N, rhs: N) -> N {
    switch (lhs, rhs) {
    case (let a, .Zero): return a
    case let (a, .Succ(b)): return .Succ(a + b)
    }
}

func *(lhs: N, rhs: N) -> N {
    switch (lhs, rhs) {
    case (_, .Zero): return .Zero
    case let (a, .Succ(b)): return a * b + a
    }
}

ここも単純なパターンマッチで実装できます．定義をすごく綺麗に実装に落とし込めるので非常に気持ちがいいです．

おまけ

playgroundなどの出力がこのようになって少し見にくいです．

let two: N = .Succ(.Succ(.Zero)))  // => Succ(N.Succ(N.Zero)

CustomLiteralConvertibleを実装すると整形できます．

extension N: CustomStringConvertible {
    var description: String {
        func toInt(n: N) -> Int {
            switch n {
            case .Zero: return 0
            case let .Succ(a): return 1 + toInt(a)
            }
        }
        return "\(toInt(self))"
    }
}