我正在尝试实现阶乘 lambda 表达式,如书中所述 Lambda-calculus, Combinators and Functional Programming
描述的方式是:
fact = (Y)λf.λn.(((is-zero)n)one)((multiply)n)(f)(predecessor)n
Y = λy.(λx.(y)(x)x)λx.(y)(x)x
哪里
(x)y is equivalent to (x y) and
(x)(y)z is equivalent to (x (y x)) and
λx.x is equivalent to (fn [x] x)
和is-zero
、one
、multiply
和predecessor
是为标准教堂数字定义的。实际定义here .
我将其翻译为以下内容
(defn Y-mine [y] ; (defn Y-rosetta [y]
((fn [x] (y (x x))) ; ((fn [f] (f f))
(fn [x] ; (fn [f]
(y ; (y (fn [& args]
(x x))))) ; (apply (f f) args))))))
和
(def fac-mine ; (def fac-rosetta
(fn [f] ; (fn [f]
(fn [n] ; (fn [n]
(is-zero n ; (if (zero? n)
one ; 1
(multiply n (f (predecessor n))))))) ; (* n (f (dec n)))))))
注释掉的版本是 Rosetta code 中的等效 fac 和 Y 函数。 .
问题 1:
我从其他地方阅读到Y-rosetta
β-还原为Y-mine
。在这种情况下,为什么最好使用其中一种而不是另一种?
问题2:
即使我使用Y-rosetta
。当我尝试时出现 StackOverflowError
((Y-rosetta fac-mine) two)
同时
((Y-rosetta fac-rosetta) 2)
工作正常。
无保护递归发生在哪里?
我怀疑这与 clojure 中 if
形式的工作方式有关,它并不完全等同于我的 is-zero
实现。但我自己还没能找到错误。
谢谢。
更新:
考虑到@amalloy的回答,我稍微改变了fac-mine
以采用惰性参数。我对 clojure 不太熟悉,所以这可能不是正确的方法。但是,基本上,我让 is-zero
采用匿名零参数函数并评估它返回的任何内容。
(def lazy-one (fn [] one))
(defn lazy-next-term [n f]
(fn []
(multiply n (f (predecessor n)))))
(def fac-mine
(fn [f]
(fn [n]
((is-zero n
lazy-one
(lazy-next-term n f))))))
我现在收到一条错误消息:
=> ((Y-rosetta fac-mine) two)
ArityException Wrong number of args (1) passed to: core$lazy-next-term$fn clojure.lang.AFn.throwArity (AFn.java:437)
考虑到 lazy-next-term
总是用 n
和 f
调用,这看起来真的很奇怪
最佳答案
fac-mine
的主体看起来错误:它调用 (is-zero n one)
产生副作用,然后无条件调用 (multiply n ( f(前任 n)))
。想必您想要在这里有一个条件选择(尽管考虑到您对 is-zero
的定义,我不明白为什么这不会引发 arity 异常)。
关于clojure - 教堂数字的阶乘函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13905851/