SwiftでZipper - 2
前回の続き。 前回はgoLeftとgoRightを実装し、部分木をたどっていくことに成功しました。 では次に逆方向に戻る事を考えましょう。といってもこのままでは戻れません。 それは情報が足りないからです。
今一度goLeft()の実装を振り返ります。
func goLeft() -> TreeInfo<T> {
switch tree {
case let .Node(_, l, _):
var insertedCrumbs = crumbs
insertedCrumbs.insert(.L, atIndex: 0)
return TreeInfo(l, insertedCrumbs)
case .Empty:
return self
}
}注目すべきは3行目のcase文。次に着目する部分木以外の情報を廃棄しているのです。 逆方向に戻るためには、着目する部分木以外の情報も保持しないとなりません。そのため、 以下のように定義を変更します。
/// Old --------------------------
enum Direction: String {
case L
case R
}
typealias Breadcrumbs = [Direction]
struct TreeInfo<T> {
let tree: Tree<T>
let crumbs: Breadcrumbs
...
}
/// New --------------------------
enum Crumb<T> {
case LeftCrumb(T, Tree<T>)
case RightCrumb(T, Tree<T>)
}
struct Zipper<T> {
let tree: Tree<T>
let crumbs: [Crumb<T>]
...
}LかRという情報しか無かったのですが、要素とTree<T>を持ちます。これは分岐する箇所の要素と、 移動しない方向の木を表します。
新しく定義したZipper<T>を用いてまずはgoLeft()を書き直します。 前回のgoLeft()も併記して何が変わったのか確認しましょう。
/// Old
func goLeft() -> TreeInfo<T> {
switch tree {
case let .Node(_, l, _):
var insertedCrumbs = crumbs
insertedCrumbs.insert(.L, atIndex: 0)
return TreeInfo(l, insertedCrumbs)
case .Empty:
return self
}
}
/// New
func goLeft() -> Zipper<T> {
switch tree {
case let .Node(x, l, r):
var insertedCrumbs = crumbs
insertedCrumbs.insert(.LeftCrumb(x, r), atIndex: 0)
return Zipper(l, insertedCrumbs)
case .Empty:
return self
}
}このように比較するとあまり違いがないことは明白です。 .Lを作成する箇所で、無視していた要素を使って.LeftCrumbs(x, r)を作成しているぐらいです。
これで逆方向に戻る準備はできました。逆方向に戻るインスタンスメソッドgoUp()はこのように書けます。
func goUp() -> Zipper<T> {
guard let latest = crumbs.first else {
return self
}
var deletedCrumbs = crumbs
deletedCrumbs.removeFirst()
switch latest {
case let .LeftCrumb(x, r):
return Zipper(.Node(x, self.tree, r), deletedCrumbs)
case let .RightCrumb(x, l):
return Zipper(.Node(x, l, self.tree), deletedCrumbs)
}
}先ほどのgoLeft()を見るとわかる通り、crumbs.firstに直前の移動パターンを入れています。そのため、 crumbs.first == nilの場合は既に最上階層にいる場合であるためselfを返し、 それ以外はcrumbs.firstが.LeftCrumbか.RightCrumbかに応じて新しくZipperを作って返します。 その時crumbs.firstに上階層の情報が入っているため上階層に戻れるわけです。
goUp()を用いれば一気に最上階層に行くメソッドtopMost()も簡単に実装できます。
func topMost() -> Zipper<T> {
guard let _ = crumbs.first else {
return self
}
return self.goUp().topMost()
}crumbs.firstが無くなるまでself.goUp().topMost()を繰り返せばいいわけです。
ついでに今いる階層の要素を書き換えるインスタンスメソッドmodify()を作成してみます。
func modify(f: T -> T) -> Zipper<T> {
switch tree {
case let .Node(x, l, r):
return Zipper(.Node(f(x), l, r), self.crumbs)
case .Empty:
return self
}
}
func modify(x: T) -> Zipper<T> {
return self.modify{ _ in x }
}これにより例えば右に行って左に行って、そこの要素を書き換えてトップまで戻ってきた木はこのように書けます。
非常にシンプルな記述です。
以上でZipperの解説は終わります。 これらがなぜZipperと呼ばれるかは、
こうしてみるとZipperという名前の由来にも納得がいきますね。 ジッパーのスライダーが上下に動いている様子にほんとそっくりです。
とのこと。確かに。