1. 関数の基本
処理をまとめる時に活用されるのが 関数 である。関数は多くの主要なプログラミング言語で標準的に実装されており、入力を与えると対応する出力を返す。
関数の利点として、以下の2つが挙げられる。
-
処理の再利用：一度定義すれば、同一プロジェクト内で何度でも呼び出すことができるため、同じ処理を繰り返し記述する必要がない
-
処理の抽象化：複雑で煩雑な処理を「ひとつの名前」を与えた関数に隠蔽することで、利用者は内部の詳細を意識せずに呼び出せる
関数は通常、呼び出しのたびに同じ入力に対して同じ出力を返す「状態を持たない存在」であるので、処理を追いやすい一方で、実行の履歴や内部状態を保持しながら処理を行いたい場合には、クロージャやクラスといった仕組みが用いられる。
クロージャは関数の外部スコープにある変数を「記憶」することで、関数に状態を持たせることができる。クラスはデータ（属性）と処理（メソッド）を一つにして、複雑な状態管理をより体系的に扱えるようにする。
2. クロージャ
クロージャをPythonで実装したものを次に示す。
def counter(x):
count = x
def inner_func():
nonlocal count # 外部のスコープにある変数 count を参照する
count += 1 # カウントを+1する
return count
return inner_func # ここでは内部の関数を返す
func = counter(0)
print(func()) # 1
print(func()) # 2
print(func()) # 3
for ループを回したり、呼び出すときに入力を変更させていないが、出力結果が呼び出すたびに異なる。
初めに、counter(0) を呼び出した時点で、counter 関数の内部変数 count に 0 がセットされ、その後内部関数の inner_func を返す。この時点で、変数 func には inner_func が格納されている。
変数 func を実行すると、counter 関数の外側スコープにある変数（= count）への参照が生きているので、nonlocal count によって、その値を補足し、更新することができる。関数呼び出しが終わっても、count は破棄されず、次回呼び出し時に前回の続きから使われるため、結果が呼び出すたびに異なる。
3. 使用例
【問題】
N個の整数が与えられる。このうち、R個の組み合わせを全列挙する。この時、組み合わせは 辞書順（インデックス昇順） で出力するものとする。【制約】
- $1 \leq N \leq 25$
- $0 \leq R \leq N$
- $A_i$ は任意の整数
Pythonの解答例を次に示す。
def next_bit_combination(initial: int):
x = initial
def inner_func():
nonlocal x
c = x & -x
r = x + c
x = (((r ^ x) >> 2) // c) | r
return x
return inner_func
N, R = map(int, input().split())
A = list(map(int, input().split()))
MAX_MASK = 1 << N
current_mask = (1 << R) - 1 # R=3の時、最初の組合せ (000...0111)
gen = next_bit_combination(current_mask)
while current_mask < MAX_MASK:
pair = []
for i in range(N):
if (current_mask >> i) & 1:
pair.append(A[i])
print(pair)
current_mask = gen()
組合わせの列挙には、bit 演算による Gosper’s hack のアルゴリズムを使用している。
このアルゴリズムは、組み合わせを「Nビットの数値マスク」として表すと、$R=3$ の場合は例えば 011 （=3番目までの要素を選ぶ）から始めて、次の組み合わせは 101 になる。
011 (2進数, 3)
↓
101 (2進数, 5)
↓
110 (2進数, 6)
この「次の組み合わせ」を全探索せずに直接求める事が出来るのが、Gosper's hack である。
通常は for ループや全探索で実装しがちな処理だが、ここでは クロージャ を用いて「次の組合せマスク」を状態として保持し、呼び出すたびに次を返すようにしている。これにより、呼び出し側は余計な状態管理を意識せず、gen() を繰り返すだけで全組合せを列挙できる。
まとめると、クロージャを使うことで「状態を外部にさらさずに保持しつつ処理を進める」ことができる。
今回の組合せ列挙の例は、その利点を実感できる一つの実用例である。
4. 参考資料
[1]. Gosper's hack
[2]. Python Closures: Common Use Cases and Examples