Swift でクロージャーを再帰的に実行できるようにする。

Swift プログラミング

Swift で let を使って定義したクロージャーは再帰実行できません。

そこで var を使って再帰実行する方法と、仲介関数を使って let 定義のクロージャーを再帰実行する方法を記してみました。

Swift言語では、次のようにlet を使ってクロージャーを定義した場合、その内部で自分自身を呼び出すことができません。

たとえば、次のような階乗を計算するfactorial関数をクロージャーで作成すると、ビルドエラーになります。

let factorial = { (value:UInt) -> UInt in
	
	if value == 0 {
		
		return 1
	}
	else {
		
		return value * factorial(value - 1)
	}
}

このときに発生するビルドエラーは、次の通りです。

Variable used within its own initial value

クロージャーを再帰実行できない理由は、クロージャーを変数に格納しようとしている「初期化」の最中に、その格納先の変数を内部で使おうとしていることが原因です。

再帰的な処理を書きたいときに、自分自身を呼び出せないのは不都合なので、再帰的にクロージャーを呼び出せるようにしてみます。

階乗というのは 1 から指定した数までを順番に掛け合わせた値です。

上記の例では再帰呼び出しを使用して、指定した値 (value) と、それよりひとつ前の階乗の値 (factorial(value - 1)) を自分自身で新たに計算した結果を掛け合わせることで、すべての数を掛け合わせています。指定値が 0 になった時点で、自分自身は呼び出さずに 1 を結果として返して、計算が終了します。

クロージャーを再帰的に呼び出す簡単な方法

クロージャー内で自分自身（を格納している変数）を使うためには、クロージャー変数の定義とクロージャー値の設定を分離する必要があります。

変数の定義と値の設定を分離する

分離するのは簡単で、まずは代入予定のクロージャーの型で変数を定義して、その後でクロージャーを設定します。このとき、後でクロージャーを設定できるようにvar で宣言し、変数の型には初期化しないでおける（クロージャーを設定せずにnil を入れておける）ように ! をつけておきます。

var factorial:((UInt) -> UInt)!

こうしたら、あとは先ほどと同じように、クロージャーを実装します。

factorial = { (value:UInt) -> UInt in

	if value == 0 {
		
		return 1
	}
	else {
		
		return value * factorial(value - 1)
	}
}

`let` を使って定義したときとの違い

先ほどとの違いといえば、既に変数factorial は定義されているので、そこにクロージャーを代入しているところです。

内部では相変わらずfactorial関数を呼び出していますが、この識別子は既にクロージャー変数として手前で宣言されているため、クロージャー内でそれがキャプチャされて、利用できるようになっています。

クロージャーを変数に代入している時点では、まだ変数factorial の値はnil ですが、この後で実際に使うときにはクロージャーの値が格納されているため、期待どおりに再帰呼び出しが行えます。

let value = factorial(5)

クロージャーを`let` で定義したい場合

上記の方法なら特に難しいことなくクロージャーを再帰的に呼び出すことができますが、せっかくのSwift なのだから、不必要に変数をvar で宣言してスコープ内を泳がせたくない場合も多いと思います。

var を使わずに、クロージャーを再帰的に使用するには、少し工夫が必要になります。

実装の方向性

実装にあたっては、再帰実行を仲介する関数をひとつ用意します。

そのとき、その内部では上記のvar を使った方法を使用しますが、そのvar は関数内部で閉じられるため、不必要に変数を泳がせなくて済むのが多少のメリットでしょうか。

また、宣言と定義を 1 行で書けるようになるので、すっきりしたコードが書けるという利点もあります。

実行したいクロージャーでは、引数で次に実行するクロージャーを受け取るようにする

let だけで再帰呼び出し可能なクロージャーを定義しようとした場合、問題になるのが『自分自身が定義の途中のため、その内側で自分自身を使えない』というところでした。

そこで、計算に必要な引数 (value) と合わせて、値を渡すと自分自身の実装内容で結果を計算してくれるクロージャー (closure) を受け取るようにします。

そうすることで、内部で自分自身を再帰的に実行したいときには、引数に渡されてきたクロージャー (closure) を実行すれば良いので、自分自身を呼び出す必要がなくなります。

let factorialImp = { (closure:UInt -> UInt, value:UInt) -> UInt in

	if value == 0 {
		
		return 1
	}
	else {
		
		return value * closure(value - 1)
	}
}

型の整理

このまま話を進めていっても良いのですが、扱う型にクロージャーが多いのと、今回の例では引数と戻り値がどちらもUInt型で判別しにくいので、次のように型エイリアスを定義して話を進めることにします。

typealias Value = UInt
typealias Result = UInt
typealias Closure = Value -> Result

こうしたとき、上記のクロージャーは次のように書き換えられます。

let factorialImp = { (closure:Closure, value:Value) -> Result in

	if value == 0 {
		
		return 1
	}
	else {
		
		return value * closure(value - 1)
	}
}

クロージャーの引数にクロージャーを渡す関数を作る

クロージャーは定義できましたが、実行時には値と一緒に、次に呼び出すクロージャーとして本来実行したいクロージャーを渡さなくてはいけません。

そのために、それを仲介する役目の関数をひとつ実装します。

最終的には、目的のクロージャーを返すようにする

let を使ってクロージャーを再帰的に利用する工夫として、まず強く意識しておきたいのが、最終的に実行したいクロージャー本来のインターフェイスを返すようにします。

本来のインターフェイスというのは、今回の階乗を計算するクロージャーであれば、冒頭のvar を使って実装した通りの、UInt型を受け取ってUInt型を返す、つまりUInt -> UInt というインターフェイスです。

そうすることで、最終的な結果を受け取ってlet で変数に格納したとき、それがクロージャーになっているので、本来のクロージャーとして使える（再帰実行するときに使うクロージャーを渡さなくても、引数を渡して結果を得られる）ようになります。

今回はtypealias を使って、本来のクロージャーを意味するUInt -> UInt にClosure という別名を割り当てていますので、以下の例では別名の方を使用します。

引数では、実行用のクロージャーと値を受け取るようにする

先ほど、クロージャーをlet で扱うと内部で自分自身を呼び出せない都合で、引数で本来のクロージャーを受け取るクロージャーを定義しました。仲介する関数では、引数としてこれを受け取ります。

つまり、実行用のクロージャーを受け取って、本来のクロージャーを返す関数を作ります。

クロージャーを返す関数なので、戻り値はさきほどtypealias で定義したClosure を指定しています。つまり今回ではUInt -> UInt を返す関数になります。

func recursiveClosure(factorialImp: (Closure, Value) -> Result) -> Closure {

	var closure:Closure!
	
	closure = { (value:Value) -> Result in
		
		return factorialImp(closure, value)
 	}
	
	return closure
}

このとき、戻り値として返すクロージャーは、内部でvar closure:Closure! で定義したクロージャーを使っています。

このクロージャーclosure では、受け取った実行用のクロージャーfactorialImp を呼び出すようにしています。実行用のクロージャーを呼び出すときには、そのさらに内部で呼び出すクロージャーを渡す必要がありますが、ここで自分自身（closure ）を再帰的に渡すようにしています。

自分自身では、内部で実行用のクロージャーfactorialImp が呼び出される実装になっているため、結果的に本来の実装が再帰的に実行できます。

実行用のクロージャーから、本来のクロージャーを取得する

仲介用のrecursiveClosure関数を定義できたら、あとは次のようにして、再帰的に実行できるクロージャーを宣言できます。クロージャーで実行する内容は、実行用に定義したクロージャーfactorialImp を渡します。

let factorial = recursiveClosure(factorialImp)

これで、次のようにしてクロージャーを実行できます。

let value = factorial(5)

上記ではクロージャー変数factorial の定義と、その実装factorialImp の定義の 2 つが必要になっていますが、これを一つにまとめて、次のように書くことができます。

let factorial = recursiveClosure { (closure:Closure, value:Value) -> Result in

	if value == 0 {
		
		return 1
	}
	else {
		
		return value * closure(value - 1)
	}
}

これで、再帰実行が可能なクロージャーfactorial がlet で定義できました。

理解しきれていないのですが、このような実装は、closure(recursiveClosure(closure)) = recursiveClosure(closure) を満たすrecursiveClosure関数を作ることで、再帰呼び出しを実現させているそうです。このようなrecursiveClosure関数のことを「不動点コンビネーター」と言うようです。

仲介関数を汎用化する

これまでの実装では、仲介関数の引数の型と戻り値の型が固定されているため、このままだと実行したいクロージャーの型が違うたびに、それ用の仲介関数を用意しなくてはいけません。

typealias Value = UInt
typealias Result = UInt
typealias Closure = Value -> Result

func recursiveClosure(factorialImp: (Closure, Value) -> Result) -> Closure {

	var closure:Closure!
	
	closure = { (value:Value) -> Result in
		
		return factorialImp(closure, value)
 	}
	
	return closure
}

仲介関数をジェネリックを使って汎用化する

ここで、typealias ではなくジェネリックを使用することで、任意の型に対応できる仲介関数を作れます。

変更箇所は、基本的にはtypealias で定義した型名、Value とResult を、ジェネリックを宣言する<> の中で<Value,Result> のように指定します。

ただ、これまでならさらにtypealias Closure = Value -> Result として使っていましたが、ジェネリック関数の宣言には定義が間に合わないので、宣言では別名Closure ではなく、置き換え前のValue -> Result で記載しています。

func recursiveClosure<Value, Result>(factorial: (Value -> Result, Value) -> Result) -> (Value -> Result) {
	
	typealias Closure = Value -> Result
	
	var closure:Closure!

	closure = { (value:Value) -> Result in
		
		return factorial(closure, value)
	}
	
	return closure
}

これで、引数の型も戻り値の型も自由に指定できる関数になりました。

使い方はこれまで通りです。

typealias Value = UInt
typealias Result = UInt

let factorial = recursiveClosure { (closure:Value -> Result, value:Value) -> Result in

	if value == 0 {
		
		return 1
	}
	else {
		
		return value * closure(value - 1)
	}
}

仲介関数のそのほかの使用例

let で再帰呼び出し可能なクロージャーを作るには、仲介用の関数をひとつ用意しておかないといけない分、var を使ったときと比べて不便にも感じられますが、あらかじめ汎用化しておくことで、いくつかのメリットも得られます。

複数の引数をとるクロージャーを再帰実行したいとき

汎用化した仲介関数は、複数の引数をとるクロージャーでも利用できます。

ただ、仲介関数がとれる引数がValue のひとつだけになっているので、タプルを使って、ひとつの引数で複数の値をまとめて扱う必要があります。

enum Pole : String {
	
	case A = "A"
	case B = "B"
	case C = "C"
}

typealias Value = (numberOfDisc:UInt, fromPole:Pole, toPole:Pole, throughPole:Pole)

let hanoi = recursiveClosure { (closure:Value -> Void, value:Value) -> Void in
	
	if value.numberOfDisc >= 1 {

		closure((value.numberOfDisc - 1, value.fromPole, value.throughPole, value.toPole))
		
		println("Disc #\(value.numberOfDisc): moved from \(value.fromPole.rawValue) to \(value.toPole.rawValue)")
		
		closure((value.numberOfDisc - 1, value.throughPole, value.toPole, value.fromPole))
	}
}

hanoi((4, .A, .B, .C))

値を渡すときに、タプルにまとめるためにカッコが余計に必要なのが不恰好ですが、ともかくこれで複数の値を扱うクロージャーを、先ほど作成した仲介関数で扱うことができました。

ちなみに上記の例のように、戻り値を必要としないクロージャーであっても、戻り値をVoid にすることで実行可能です。

引数や戻り値の型を書かずに呼び出す

仲介関数があれば、それがとるクロージャーの型を Swift が推論できるようになるため、内容を 1 行で書けるクロージャーでは、記述が大幅に簡素化できます。

たとえば次のクロージャーについて見ていきます。

let factorial = recursiveClosure { (closure:UInt -> UInt, value:UInt) -> UInt in

	if value == 0 {
		
		return 1
	}
	else {
		
		return value * closure(value - 1)
	}
}

まず、このクロージャーの実装は、三項演算子を使って 1 行にまとめられます。

let factorial = recursiveClosure { (closure:UInt -> UInt, value:UInt) -> UInt in

	return value == 0 ? 1 : value * closure(value - 1)
}

すると実装が 1 行になるので、戻り値を意味するreturn と、その型を意味する宣言部の-> UInt を省略できます。

let factorial = recursiveClosure { (closure:UInt -> UInt, value:UInt) in

	value == 0 ? 1 : value * closure(value - 1)
}

そして、今回は仲介関数が 2 つの引数をとることが定義でわかっているため、宣言部分の引数リスト (closure:UInt -> UInt, value:UInt) とそれに続くin を省略できます。

引数リストを省略すると、最初の引数を $0 で、その次を $1 で、扱えます。

これを踏まえて、次のようにコードを書き換えられます。

let factorial = recursiveClosure {

	$1 == 0 ? 1 : $1 * $0($1 - 1)
}

途端に分かりにくくなりましたが、慣れ次第では読みやすいコードになる場合があります。

あくまでも今回の仲介関数に限ったつじつまあわせの理屈ですが、コマンドラインとかでよくある規則で $0 が自身のコマンド名を表していて、それに与えられた引数が $1 で得られる環境があったりします。そう考えると、今回は $1 は引数（目的の値）で、$0 は自身のコマンド名（再帰実行で使うクロージャー）で、けっこう自然にまとまっているとも言えなくはありません。

そしてもうひとつ興味深いのが、上記のコードはクロージャーがまったく型に関与していないところです。

引数リストを明記すれば $1 等もそれに従うことになるのですが、引数リストを省略すると、引数の型は定義に従います。今回の仲介関数はジェネリックになっているため $1 等も汎用的な状態を維持します。

そして、実際に型が決まるのは、クロージャーを使うときです。

let value = factorial(5)

こうしたときに $1 の型が、今回であればInt型に定まるため、それから計算結果の型が決まり、数珠繋ぎに $0 の型も決まって、利用できるようになります。

こうして計算結果を得られるようになるため、もともとはUInt型を想定したコードの型を省略して行ってましたが、上記の理由でいつのまにか、計算結果がInt型で得られるようになっています。

もちろん、実装が受け取った型を処理できない場合はビルドエラーになり、実行できません。