Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

Pythonのlambdaだけで、Schemeのcond(条件分岐)っぽいものを実装する長い道のり

はじめに

 最近はずっとScheme(いわゆるLispの方言)とかそういうのをいじっていたせいなのか、「あー、関数型っぽく考えてえなあ」という、いわゆる関二病(関数型言語を勉強して二ヶ月目にかかる病気)になってしまっていた。で、そういった「関数型」によくあるアプローチをPythonで書き直した場合は、どういう形になるのだろうか、と思ったので、興味がてら、幾つかのサンプルを書いてみる。最初に、condを実装してみようと思う。

 ちなみに、同じようなことを過去に考えていた人はいたようで、fn.pyという名前で公開されていたりします。

実装

 例えば、今から階乗を算出する関数を定義してみます。この場合、関数を定義するのに、lambdaだけしか使えない、という縛りをつけます。もちろん、既存の階乗を求める関数を使ってもいけない、とします。

 まず、単純に関数のテンプレートを考えてみます。関数のテンプレートは次のようになるはずです。

factorial = lambda x: x

 この関数は、なんらかの数字を受けとり、なんらかの数字を返すものです。さて、階乗の定義は、nからn-1の積、その結果のn-2の積……を繰り返していき、最終的に1になるまで続ける必要があります。とするならば、引数を受けとったときの最初の段階は下の通りになるはず。

factorial = lambda x: x * (x - 1)

 しかし、これだと一回目しか計算されないですね。問題は1になるまで、この掛け算を続けなきゃいけないわけです。そこで、もう一度自分自身の関数を呼び出します。

factorial = lambda x: x * (factorial(x - 1))

 これでどのようになったか。

factorial(5) -> 5 * (factorial(4)) =>
factorial(4) -> 4 * (factorial(3)) =>
factorial(3) -> 3 * (factroial(2)) => 
...

 という形で、どんどん連鎖することが可能になる。しかし、この再帰関数には終了条件、つまり呼び出さない分岐が無いので、延々と再帰し続けてしまう。なので、何処かのタイミングで分岐させる必要が出てくる。

 例えば、Pythonの場合だと、条件演算子があります。詳しい内容は、ドキュメントに見て頂ければわかると思いますので、上のfactroialのlambda式を、条件演算子を使って書き直してみましょう。

factorial = lambda x: x * (factorial(x - 1)) if x >= 1 else 1

 このように書き直した場合、xが1以下であるならば、factorialは1になります。つまり、

facotrial(3) -> 3 * (factorial(2)) =>
facotrial(2) -> 2 * (factorial(1)) =>
facotrial(1) -> 1 

 という形で終了することになります。よかったですね。そして、慧眼な人間であるならば、上のプロセスは、構造化プログラムとして、下のように書き直すことが出来るでしょう。

def factorial(x):
    result = 1
    while x >= 1:
        result *= x
        x -= 1
    return result

 上記の方法を知ってしまった私たちは、上の方法はどうも冗長のように感じますね。

 さて、欲を出して、この関数を「xが偶数のときは足し算、xが奇数の時は掛け算を行う再帰関数」として再定義し直したい、という欲が生まれたとしましょう。このとき、条件は三つになります。もし、愚直に条件演算子を使うことを考えると、次のような実装になるでしょう。

# example: 4 + (3 * (2 + 1)) => 13
factorial = lambda x: 1 if x <= 1 else x * (factorial(x - 1)) if x % 2 == 1 else x + (factorial(x - 1))

 しかし、お世辞にもこの条件演算子は読みやすいということは出来ないでしょう。というのも、どの条件に合致したときに、どの式になるのかが全くわからないからです。そこで、これらの条件を整理するためのヘルパー関数を定義してみます。

pycond = lambda *args: args[0][1] if args[0][0] else pycond(*args[1:]) 

 condは、Schemeなどで使われる条件分岐用の関数です。さっそく、この関数を試してみましょう。

In : pycond((False, 'Too Bad'), (True, 'Good'))
Out: 'Good'

 上手く機能しているようなので、さっそく関数に組み込んでみます。

# example: 4 + (3 * (2 + 1)) => 13
factorial = lambda x: pycond(
    ((x <= 1), 1),
    ((x % 2 == 0), (x + factorial(x - 1))),
    ((x % 2 == 1), (x * factorial(x - 1))),)

 しかし、この場合は上手くいきません。これはSICPの問題でも出てくるのですが、関数に対して引数に式を渡してあげると、まず「その式がどのような値なのか」を調べるために計算し始めます。つまり、上記の場合だと、式を渡しているつもりになっていたが、実際には評価が実行されてしまっていたという失敗です。

 これを回避する方法が一つあります。関数が値として表現されるタイミングというのは、その関数が「呼び出された」タイミングです。関数が呼び出されるまでは、「関数オブジェクト」のままになります。ということは、関数の評価を遅延させるためには、関数オブジェクトと、そこに渡してやる引数は別々にわけておいて、最初にあたった関数がTrueであたったときのみ、関数と組み合わせるように改造してあげる必要がありそうです。仮に、そのような表現を与えてみましょう。

# example: 4 + (3 * (2 + 1)) => 13
factorial = lambda x: pycond(
    ((x <= 1), 1),
    ((x % 2 == 0), (add, [x, (factorial, [x - 1])])),
    ((x % 2 == 1), (mul, [x, (factorial, [x - 1])])),)

 このように、関数+引数という組み合わせのタプルを用意し、これらをあとで組み立てるという戦略を取るようにしてみましょう。まずpycondの実装に戻る前に、この関数を組み立てるための戦略を考えます。

 ここで着目したいのは、関数は一段だけではなく、引数の中に関数がある場合があるということです。なので、関数の中にtupleかlistが出てきたなら、そちらも組み立ててあげる必要があります。そして、懸命なブログの読者なら気がつかれたと思うのですが、これもまた再帰構造を取ります。

 さて、このような組み立てを実現するための関数を定義します。

func_call = lambda func, arg: func(*[func_or_value(elem) for elem in arg])

 上記を見るように、引数には関数が分解された形のものが入っているか、あるいはただの値が入っているはずです。値であるならば、その値をそのままに、もし関数が入っているとするならば、それを組み立ててあげる必要があります。ただ、関数が入っている場合は、tupleかlistの場合です。

 しかし、listやtupleだからといって、必ずしもそれが「関数+引数」の分解系であるとは限りません。なので、tupleであれ、listであれ、「関数+引数」という形になっているときのみ、組み立て可能な関数だということにします。

 条件をわかりやすくするために、まずあるオブジェクトが、tupleかlistかを判定する関数を作成します。

list_or_tuple = lambda elem: isinstance(elem, list) or isinstance(elem, tuple)
list_is_func = lambda elem: len(elem) is 2 and hasattr(elem[0], '__call__') and (list_or_tuple(elem[1]))

 そして、上記に合致したら、再帰的にfunc_callを呼び出すようにしてあげます。

func_or_value = lambda elem: func_call(*elem) if list_or_tuple(elem) and list_is_func(elem) else elem

 さて、これらを四つまとめてみましょう。

func_call = lambda func, arg: func(*[func_or_value(elem) for elem in arg])

list_or_tuple = lambda elem: isinstance(elem, list) or isinstance(elem, tuple)
list_is_func = lambda elem: len(elem) is 2 and hasattr(elem[0], '__call__') and (list_or_tuple(elem[1]))

func_or_value = lambda elem: func_call(*elem) if list_or_tuple(elem) and list_is_func(elem) else elem

 さて、これで動くかどうか、実験してみましょう。

In : func_call(foobar, [1, [foobar, [1 , [foobar, [1, 2]]]]])
Out: 5

 動いてますね!さっそく、pycondに組み込んでみましょう。

pycond = lambda *args: func_or_value(args[0][1]) if args[0][0] else pycond(*args[1:])

 すると

In : pycond((False, (foobar, [1, [foobar, [1, 2]]])), (True, (foobar, [1, [foobar, [1, 3]]])))
Out: 5

 と、答えが出てきます。では、さっそくfactorial関数を実行してみましょう。factorial関数は、下のような形でした。

# example: 4 + (3 * (2 + 1)) => 13
factorial = lambda x: pycond(
    ((x <= 1), 1),
    ((x % 2 == 0), (add, [x, (factorial, [x - 1])])),
    ((x % 2 == 1), (mul, [x, (factorial, [x - 1])])),)

 add関数とmul関数の定義を忘れていましたが、ここはOperatorのもので代用します。

from operator import add
from operator import mul

まとめ

 さて、これらの全体を足し会わせてみましょう。

# -*- coding: utf-8 -*-

from operator import add
from operator import mul

#引数の中に分解された関数がないかどうか調べる
func_call = lambda func, arg: func(*[func_or_value(elem) for elem in arg])

#関数はリストかタプルで、その長さが2、さらにその組み合わせが関数かつリストorタプル
list_or_tuple = lambda elem: isinstance(elem, list) or isinstance(elem, tuple)
list_is_func = lambda elem: len(elem) is 2 and hasattr(elem[0], '__call__') and (list_or_tuple(elem[1]))

func_or_value = lambda elem: func_call(*elem) if list_or_tuple(elem) and list_is_func(elem) else elem
pycond = lambda *args: func_or_value(args[0][1]) if args[0][0] else pycond(*args[1:])

# example: 4 + (3 * (2 + 1)) => 13
factorial = lambda x: pycond(
    ((x <= 1), 1),
    ((x % 2 == 0), (add, [x, (factorial, [x - 1])])),
    ((x % 2 == 1), (mul, [x, (factorial, [x - 1])])),)


if __name__ == '__main__':
    print factorial(4)

 なんか最終的にlispのまがいものになったような気もしなくはない……