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
思ったほど変わらないですね。
