Swiftの再帰的列挙型(Recursive Enumerations)

列挙型(Enumerations)

列挙型を使って、再帰的な構造を持ったデータ(機能)を実装することができます。これはすごいですね。かなり難しいと思いますので、公式マニュアルにある四則演算の例を流用して(ただし型はDoubleに変更、値も少し変えて)説明します。Xcodeのplaygroundを使って、実際に動かしてもらえると、再帰的列挙型(または再帰的関数)の動きが分かると思いますので、是非試してみてください。

再帰的(Recursive)ってどういう意味?

再帰的(Recursive)という表現は、プログラミングで良く使われます。どういう時に使われるかというと、例えば関数なら、ある関数の戻り値が自分自身である場合に、その関数を「再帰的関数(recursive function)」と呼びます。

再帰的関数の具体例 | 階乗計算関数factorial

例えば、階乗(factorial)という演算を考えてみます。これは与えられた自然数(非負の整数、UIntみたいなものです)に対して、以下のような計算をするものです。

// 階乗の例、6!
6! = 6*5*4*3*2*1

これを再帰的関数として実装してみると、こんな感じになります。

// 階乗を計算する再帰的関数
func factorial(_ number: UInt, _ result: UInt = 1) -> UInt {
    // numberが1以下になると落とす
    guard number > 1 else {
        return result
    }
    
    return factorial(number-1, result*number)
}

// 階乗の計算
print("6! = \(factorial(6))")
// 6! = 720

関数factorial(_:_:)の戻り値はfactorial(_:_:)です。自分自身を呼び出しているので、普通は永久にループして、プログラムを強制終了する以外は関数の実行を止める手段はありません。

無限ループになるのを防ぐ条件分岐が最初のguardです。ここでは、number <= 1という条件を満たせば、関数が止まるような仕掛けになっています(if文でも同等の条件分岐を実装できます)。第一引数が肝で、渡されたパラメータから1を引いています。

return factorial(number-1, result*number)

この処理とguard文から、関数がいつかは止まることが簡単に分かると思います。

また、第二引数では現在の入力値numberを結果resultに掛け合わせています。具体的に数字で書くと分かりやすいと思いますが、例えばnumber6にした時の1回目のreturnでは

return factorial(5,6)

です。ここでfactorial(_:_:)関数を呼び出しているので、そのreturn結果を書き下すと、

return factorial(4,6*5)

となり、この第一引数が1になるまで関数呼び出しが続くので、結果(第二引数)は6!になるのが分かると思います。

なんとなく再帰的な構造について理解できたでしょうか?これを列挙型で実装できるというのが本題です。

再帰的列挙型の例 | 2項の四則演算の場合

いきなり実際のサンプルコードを示します。公式マニュアルよりちょっとだけ複雑な計算をしたかったので、3.14 * (5.0^2 + 4.0^2)という演算をしたい場合の例です。

// 簡単な2項の四則演算が可能な、再帰的列挙型の例(Double)
enum ArithmeticExpression {
    case number(Double)
    indirect case addition(ArithmeticExpression, ArithmeticExpression)
    indirect case multiplication(ArithmeticExpression, ArithmeticExpression)
    indirect case power(ArithmeticExpression, Int)
}

// 評価関数
func evaluate(_ expression: ArithmeticExpression) -> Double {
    switch expression {
    case .number(let value):
        print("Number(\(value))")
        return value
    case .addition(let left, let right):
        print("Addition(\(evaluate(left))+\(evaluate(right)))")
        return evaluate(left) + evaluate(right)
    case .multiplication(let left, let right):
        print("Multiplication(\(evaluate(left))*\(evaluate(right)))")
        return evaluate(left) * evaluate(right)
    case .power(let value, let power):
        print("Power(\(evaluate(value))^\(power))")
        var result = evaluate(value)
        for _ in 0..<power-1 {
            result *= evaluate(value)
        }
        return result
    }
}

// 3.14 * (5.0^2 + 4.0^2)を計算
let pi = ArithmeticExpression.number(3.14)
let five = ArithmeticExpression.number(5.0)
let four = ArithmeticExpression.number(4.0)
let fiveSquare = ArithmeticExpression.power(five, 2)
let fourSquare = ArithmeticExpression.power(four, 2)
let sum        = ArithmeticExpression.addition(fiveSquare, fourSquare)
let area       = ArithmeticExpression.multiplication(pi, sum)
print("3.14 * (5.0^2 + 4.0^2) = \(evaluate(area))")
//"3.14 * (5.0^2 + 4.0^2) = 128.74"と表示

再帰的関数の例では、戻り値が自分自身でした。再帰的列挙型の場合は、associated valuesに自分自身が入ってます。このような再帰的表現を使う場合は、列挙型の値の前にindirectキーワードを使います。Indirectは「間接的な」とか「二次的な」という意味があります。

今の例では1つずつindirectキーワードを指定しましたが、列挙型全体にindirectを指定することも可能です。

indirect enum ArithmeticExpression {
    ....
}

再帰的呼び出しの確認

再帰的な列挙型の挙動を見るために、print(_:)関数を挟むと分かりやすいです。上記の例では、func evaluate(_:)がどういう風に再帰的呼び出しを行うかを確認するために、敢えてcase直下にprint(_:)関数を挟んでいます。

例えば、以下のような計算をすると、出力は

// 再帰的呼び出しの確認
let pi         = ArithmeticExpression.number(3.14)
let five       = ArithmeticExpression.number(5.0)
let four       = ArithmeticExpression.number(4.0)
let fiveSquare = ArithmeticExpression.power(five, 2)
print(evaluate(fiveSquare))
//Number(5.0)
//Power(5.0^2)
//Number(5.0)
//Number(5.0)
//25.0

という具合になります。

[図解]再帰的列挙型の呼び出し

上の図では、プログラム上のどこで出力されているかを簡単に示しました。なんとなく再帰的呼び出しの実行に関して理解できたでしょうか?実際に、自作の再帰的列挙型や関数を作って色々試行錯誤してみると、その働きが良く分かると思います。

図はSwift 2の際に作ったので、列挙型が持っている値の名前が大文字から始まっています

まとめ

  • 再帰的列挙型(Recursive Enumerations)は、associated value(s)に自分自身が入るような列挙型
  • 列挙型に再帰的な機能を実装する際にはindirectキーワードを使う