SwiftでZipper - 1
久しぶりにHaskellを復習したいという思いから、 Learn Haskell You for Great Good!を読み直しています。 ただ読み直すのも面白くないので、Swiftだとどういう実装になるのかという観点で勉強したいと思います。 (playgroundをgithubにアップしていこうと思います。)
初回はZipperパターン。いきなり最終章です(笑) というのもXcode7からindirect enumがサポートされたためです。 最初に出てくる木はこのように定義できます。
indirect enum Tree<T>{
case Empty
case Node(T, Tree<T>, Tree<T>)
}木Tree<T>は枝を示す.Nodeか、空の状態である.Emptyです。 .Nodeには更にTree<T>がぶらさがっており、好きなだけぶらさがった状態を表現できます。 本文中に出てくるfreeTreeはこのように表せます。
let freeTree: Tree<String> =
.Node("P",
.Node("O",
.Node("L",
.Node("N", .Empty, .Empty),
.Node("T", .Empty, .Empty)
),
.Node("Y",
.Node("S", .Empty, .Empty),
.Node("Y", .Empty, .Empty)
)
),
.Node("L",
.Node("W",
.Node("C", .Empty, .Empty),
.Node("R", .Empty, .Empty)
),
.Node("A",
.Node("A", .Empty, .Empty),
.Node("C", .Empty, .Empty)
)
)
)各枝には要素があり、最下層までいくと.Emptyがいます。
まずは木の状態がグラフィックでわかるようにするため、descriptionメソッドを準備することにします。
extension Tree where T: CustomDebugStringConvertible {
func description() -> String {
return self.description(0, self.stratum(0))
}
func stratum(value: Int) -> Int {
switch self {
case .Empty:
return value
case let .Node(_, l, r):
return l.stratum(value) > r.stratum(value) ? l.stratum(value) + 1 : r.stratum(value) + 1
}
}
func description(stratum: Int, _ total: Int) -> String {
let space = "__"
var pre = ""
var post = ""
for (var i = 0; i < stratum; i++){
pre += space
}
for (var i = 1; i < total - stratum; i++){
post += space
}
switch self {
case .Empty:
return ""
case let .Node(x, l, r):
return pre + x.debugDescription + post + "\n" + l.description(stratum + 1, total) + r.description(stratum + 1, total)
}
}
}これによりさきほどのfreeTreeはplayground上でこんな感じに出力されます。
それでは本文の流れに沿って進めます。 まずはwの要素をpに変えましょう。 そのままやろうとするとこんな感じになります。
func changeToP(tree: Tree<String>) -> Tree<String> {
guard case let .Node(x, l, tree2) = tree else {
return tree
}
guard case let .Node(y, tree3, r) = tree2 else {
return tree
}
guard case let .Node(_, m, n) = tree3 else {
return tree
}
return .Node(x, l, .Node(y, .Node("P", m, n), r))
}guard文の中身はfatalErrorにするとか、 もしくは返り値をTree<String>?にしてnil返すとかも考えられますが、 本筋ではないのでとりあえず同じTree<String>を返すことにします。
機能しているのを確認するとこんな感じ。
この関数をもう少しだけ一般的にします。 トップからたどって行って変えたい場所を引数として与えてやります
enum Direction: String {
case L
case R
}
func _changeToP(directions: [Direction]) -> Tree<String> -> Tree<String> {
return { tree in
if let direction: Direction = directions.first {
var dirs = directions
dirs.removeFirst()
switch direction {
case .L:
switch tree {
case let .Node(x, l, r):
return .Node(x, _changeToP(dirs)(l), r)
case .Empty:
return .Empty
}
case .R:
switch tree {
case let .Node(x, l, r):
return .Node(x, l, _changeToP(dirs)(r))
case .Empty:
return .Empty
}
}
}else {
switch tree {
case let .Node(_, l, r):
return .Node("P", l, r)
case .Empty:
return .Empty
}
}
}
}これで少しだけ柔軟になりました。変更する位置を[Direction]で指定できるからです。
ここで定義した[Direction]は方向を示したリストです。 トップ階層からどのように移動してきたのかを意味します。 つまり[Direction]のindex0の要素は直前にどのように移動したかを表しています。 これは木を逆方向にたどるのに使えそうです。 改めてBreadcrumbsとして定義することにします。
typealias Breadcrumbs = [Direction]部分木Tree<T>と移動履歴Breadcrumbsをタプルとしてワンセットに扱うことにします。 これにより木を左に操作したり右に操作したりができるようになります。
func goLeft<T>(tree: Tree<T>, _ crumbs: Breadcrumbs) -> (Tree<T>, Breadcrumbs){
switch tree {
case let .Node(_, l, _):
var insertedCrumbs = crumbs
insertedCrumbs.insert(.L, atIndex: 0)
return (l, insertedCrumbs)
case .Empty:
return (.Empty, crumbs)
}
}
func goRight<T>(tree: Tree<T>, _ crumbs: Breadcrumbs) -> (Tree<T>, Breadcrumbs){
switch tree {
case let .Node(_, _, r):
var insertedCrumbs = crumbs
insertedCrumbs.insert(.R, atIndex: 0)
return (r, insertedCrumbs)
case .Empty:
return (.Empty, crumbs)
}
}それぞれgoLeft()は左側の部分木に移動する関数、goRight()は右側の部分木に移動する関数です。 返り値にはBreadcrumbsが含まれており、どちらに移動したのかが情報として含まれます。
Breadcrumbsにもdescription()を以下のように定義して結果を参照しやすくしておきます。
extension SequenceType where Self.Generator.Element == Direction {
func description() -> String {
return self.reduce(""){ (str: String, dir: Direction) -> String in
return str + dir.description()
}
}
}すると、goLeft()は以下のようになります。
左側の部分木のみ出力され、なおかつBreadcrumbsには.Lが入っていることがわかります。
しかしこれもまた直感的ではありません。例えば、右に行って左に行く場合
goLeft(goRight(freeTree, []))
のように実際の移動に対して後ろから記述しなければならないからです。 しかしこれは演算子を定義することでリフトできます。
infix operator |> {
associativity left
}
func |> <T>(lhs: (Tree<T>, Breadcrumbs), rhs: (Tree<T>, Breadcrumbs) -> (Tree<T>, Breadcrumbs)) -> (Tree<T>, Breadcrumbs){
return rhs(lhs)
}これにより、先ほどの操作は
(freeTree, []) |> goRight |> goLeftのように書くことができます。実際に確認してみるとこんな感じになります。
もちろん、カスタム演算子を用いない方法もあります。 それはTree<T>とBreadcrumbsの両方を管理する型を別に定義します。
struct TreeInfo<T> {
let tree: Tree<T>
let crumbs: Breadcrumbs
init(_ tree: Tree<T>, _ crumbs: Breadcrumbs){
self.tree = tree
self.crumbs = crumbs
}
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
}
}
func goRight() -> TreeInfo<T> {
switch tree {
case let .Node(_, _, r):
var insertedCrumbs = crumbs
insertedCrumbs.insert(.R, atIndex: 0)
return TreeInfo(r, insertedCrumbs)
case .Empty:
return self
}
}
}
extension TreeInfo where T: CustomDebugStringConvertible {
func description() -> String {
return tree.description() + "\n" + crumbs.description()
}
}これでgoLeft()とgoRight()は自身と同じ型のオブジェクトを返すインスタンスメソッドになりました。
逆方向にたどるのは次回にします。