毎月おなじみの関西モバイルアプリ研究会で「Swiftで自然数を作るっ」という発表でライブコーディングをしました.
書いたコードは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))" } }
反省
LTなのに15分かかった.