読者です 読者をやめる 読者になる 読者になる

ラムダ式で再帰関数を書く

計算機 Python

Java8で導入されたと話題のラムダ式を勉強中。コーディングの観点からはただの無名関数以上の意味はないが、いろいろ深いみたい。

Pythonだと以下のように書く

>>> add = lambda x, y: x + y
>>> add(1, 2)
3

では、再帰関数はどうすればよいのだろう?

例えば、階乗は

>>> factorial = lambda n: n * factorial(n-1) if n > 0 else 1
>>> factorial(5)
120

と書ける。しかし、

>>> f = factorial
>>> factorial = None
>>> f(5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
TypeError: 'NoneType' object is not callable

内部で一時的につけた名前を呼び出しているので、代入することができない。そして、名前をつけちゃっているので、無名関数とは呼べない。これは困る。どうしたものか?

こういうこと考えてた人がいたらしく答えが用意されていた:不動点コンビネータである。

以下のようなZコンビネータを用意します。

>>> Z = lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y)))

そして、階乗の関数を返す関数(高階関数)を用意します。

>>> Factorial = lambda f: lambda n: n * f(n-1) if n > 0 else 1

高階関数をZコンビネータにかますとなんと無名の再帰関数が作れちゃいます。

>>> factorial = Z(Factorial)
>>> factorial(5)
120

これだと無名ではないので、一行で書くと、

>>> (lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y))))(lambda f: lambda n: n * f(n-1) if n > 0 else 1)(5)
120

理屈は分かるが、複雑すぎる。こんなのコードに埋め込まれた日には、えらいことになる。こんなの絶対流行らない。言語として使わせたいなら、不動点コンビネータは組み込みで定義されているはずだ。

そして、パフォーマンスも悪そう。試してみよう。

>>> from timeit import timeit
>>> timeit('fact(10)', 'Z = lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y))); fact = Z(lambda f: lambda n: n * f(n-1) if n > 0 else 1)')
11.28494119644165
>>> timeit('fact(10)', 'fact = lambda n: n * fact(n-1) if n > 0 else 1')
2.4460370540618896

思ったほど変わらないですね。

参考

時間城年代記:PythonによるYコンビネータの仕組みの(多分)わかりやすい説明