uフィボナッチの組み合わせ:このコードをPythonにどのように翻訳しますか?
-
29-09-2019 - |
質問
私はコンビネーターについて学ぼうとしています、そして、私は与えられた例を理解するのに苦労しています(yオーバーライドの自己適用)。私は概念を把握し始めていると思いますが、私はまだ理解にはほど遠いです。
次のコードをPythonに翻訳したいと思います。
(define (U f) (f f))
(define (fib-nr f)
(lambda (n)
(if (< n 2) 1 (+ ((f f) (- n 1)) ((f f) (- n 2))))))
# Usage:
((U fib-nr) 35) ;==> 14930352
私は書くことによって「文字通り」翻訳を試みました:
U = lambda u: u(u)
def fibnr(f):
return lambda n: 1 if (n<2) else (f (f (n-1))) + (f (f (n-2)))
しかし、これは機能しません(機能がラムダ内で評価される順序に関係していると思います)。
それで、私は関数の構成を次のように使用しようとしました:
# http://code.activestate.com/recipes/52902-function-composition/
class compose:
'''compose functions. compose(f,g,x...)(y...) = f(g(y...),x...))'''
def __init__(self, f, g, *args, **kwargs):
self.f = f
self.g = g
self.pending = args[:]
self.kwargs = kwargs.copy()
def __call__(self, *args, **kwargs):
return self.f(self.g(*args, **kwargs), *self.pending, **self.kwargs)
U = lambda u: compose(u, u)
def fibnr(f):
ff = compose(f, f)
return lambda n: 1 if (n<2) else (ff (n-1)) + (ff (n-2))
しかし、まだうまくいきませんでした、コードの最後のスニペットを呼び出すとき、私はラムダを取り戻します:
>>> U(fibnr)(35)
<function <lambda> at 0x01A1B6B0>
それで、Pythonで与えられた例の「文字通り」翻訳を書くことは可能ですか?どうすればできますか?
解決
私は正しい結果を生み出すように見える簡単な翻訳を書きました:
def U(f): return f(f)
def fibnr(f):
def lam(n):
if (n < 2): return 1
return f(f)(n-1) + f(f)(n-2)
return lam
または、あなたが本当にラムダスが好きなら:
def fibnr(f): return lambda n: 1 if (n < 2) else f(f)(n-1) + f(f)(n-2)
あなたの最初の問題はLISPの翻訳だったと思います ((f f) x)
Pythonに f(f(x))
それ以外の f(f)(x)
.
コンビネーターを理解してください:)
所属していません StackOverflow