たらいまわし関数 - 技術をかじる猫

いまさらかもしれないが、関数型言語勉強会で、たらいまわし関数についてやってたので、Pythonでどうにかしてみた。
というのも、現場でPythonを使った回答がうまく出来なかった為、リベンジしようという話。

Haskell のたらいまわしtmaeda 日記
 C++でたらいまわしドレッシングのような
 C#でたらいまわし(hatena (diary ’Nobuhisa))

参考リンクたち。
それぞれの特性をまず考察。
Haskell のたらいまわしは、間違いなく遅延評価の恩恵。
C++ 版のものは、爆速で驚いたが、結局コンパイル時に計算している為、実際には回答を print していることに。
bool がミソで、メモ化しているということらしい。（教えて下さった方sumim’s smalltalking-tos
ご本人に言わせれば、遅延評価は内部的にメモ化に近いことをしているので、厳密に処理系実装の速度比較としては有用ではないとのこと）
C# 版で見てみると、通常版とクロージャによる実装の2通りがある。

# 基本的なたらい回し
def tarai(x, y, z):
    if x <= y: return y
    return tarai(tarai(x - 1, y, z),
                 tarai(y - 1, z, x),
                 tarai(z - 1, x, y))

if __name__ == "__main__":
    print(tarai(20,10,5))
    raw_input()

正直、実行速度に耐えないｗ
C# 版のクロージャ実装をみるとき、LazyInt なるものを宣言している。引数に関数を渡す為の工夫ということか。

ならばクロージャ実装！

# クロージャ的？
def tarai(x, y, z):
    if x <= y: return y
    z_lazy = z()
    return tarai(tarai(x - 1, y, lambda : z_lazy),
                 tarai(y - 1, z_lazy, lambda : x),
                 lambda : tarai(z_lazy - 1, x, lambda : y))
if __name__ == "__main__":
    print(tarai(20,10,lambda : 5))
    raw_input()

z_lazy = z()
するまで、z の値は評価しない、で、lambda でとにかく計算するべき処理をスタックに積んでしまうと。

やってみるとわかるけど爆速。でも「lambda : 5」はどうにかならんか（−−；

で、メモ化について考えてみる。
メモ化は、関数に渡された引数パターンを記録して、同じ引数パターンの場合は計算しないと。
そうすることで、異常に深くなる関数スタックの輪を断ち切るとか、、、、。

# メモとってみる

memo_dic = {}

def tarai(x, y, z):
    global memo_dic
    pat = (x, y, z)
    if not pat in memo_dic:
        if x <= y:
            memo_dic[pat] = y
        else:
            memo_dic[pat] = tarai(tarai(x - 1, y, z),
                                  tarai(y - 1, z, x),
                                  tarai(z - 1, x, y))
    return memo_dic[pat]

if __name__ == "__main__":
    print(tarai(20,10,5))
    raw_input()

「pat」で引数パターンを作成して、それをキーに辞書登録。
こうして必要以上の処理をしないっと。

しかし、、、もっとエレガントな書き方できないんだろーか、、、考察の余地アリ。