我可以在 Clojure 中的这个函数组合实现中使用 `recur` 吗？
Can I use `recur` in this implementation of function composition in Clojure?
考虑 Clojure 中 comp 的这个简单的递归实现：
(defn my-comp
([f]
(fn [& args]
(apply f args)))
([f & funcs]
(fn [& args]
(f (apply (apply my-comp funcs) args)))))
有人告诉我，正确的方法是使用 recur，但我不确定 recur 是如何工作的。特别是：有没有办法让上面的代码成为 recurable?
一种方法是重新安排此代码以将一些中间函数传递回 recur 的定义。
模型应该是这样的：
(my-comp #(* 10 %) - +)
(my-comp (fn [& args] (#(* 10 %) (apply - args)))
+)
(my-comp (fn [& args]
((fn [& args] (#(* 10 %) (apply - args)))
(apply + args))))
最后一个 my-comp 将使用第一个 my-comp 重载（即 (my-comp [f])
它可能是这样的：
(defn my-comp
([f] f)
([f & funcs]
(if (seq funcs)
(recur (fn [& args]
(f (apply (first funcs) args)))
(rest funcs))
(my-comp f))))
请注意，尽管不是可能的 apply 目标，recur 形式仍然可以接受作为序列传递的可变参数。
user> ((my-comp (partial repeat 3) #(* 10 %) - +) 1 2 3)
;;=> (-60 -60 -60)
但是，请注意，实际上这个实现并不比你的好：虽然 recur 使你免于函数创建时的堆栈溢出，但它仍然会在应用程序中溢出（有人，请纠正我，如果我我错了）：
(apply my-comp (repeat 1000000 inc)) ;; ok
((apply my-comp (repeat 1000000 inc)) 1) ;; stack overflow
所以使用 reduce 或其他东西可能会更好：
(defn my-comp-reduce [f & fs]
(let [[f & fs] (reverse (cons f fs))]
(fn [& args]
(reduce (fn [acc curr-f] (curr-f acc))
(apply f args)
fs))))
user> ((my-comp-reduce (partial repeat 3) #(* 10 %) - +) 1 2 3)
;;=> (-60 -60 -60)
user> ((apply my-comp-reduce (repeat 1000000 inc)) 1)
;;=> 1000001
上面已经有很好的答案了，不过我觉得当初建议用recur可能是想着更加手动的积累结果。如果您还没有看到它，reduce 只是 loop/recur:
的一个非常具体的用法
(ns tst.demo.core
(:use demo.core tupelo.core tupelo.test))
(defn my-reduce
[step-fn init-val data-vec]
(loop [accum init-val
data data-vec]
(if (empty? data)
accum
(let [accum-next (step-fn accum (first data))
data-next (rest data)]
(recur accum-next data-next)))))
(dotest
(is= 10 (my-reduce + 0 (range 5))) ; 0..4
(is= 120 (my-reduce * 1 (range 1 6))) ; 1..5 )
一般来说，可以有任意数量的循环变量（不像reduce 那样只有2 个）。使用 loop/recur 为您提供了一种更“实用”的方式来循环累积状态，而不是使用 and atom 和 doseq 或其他东西。顾名思义，从外部看，效果与普通递归非常相似 w/o 任何堆栈大小限制（即 tail-call 优化）。
P.S. 正如这个例子所示，我喜欢使用 let 形式来非常明确地命名为下一次迭代生成的值。
P.P.S. 而编译器会让你输入以下w/o混淆：
(ns tst.demo.core
(:use demo.core tupelo.core tupelo.test))
(defn my-reduce
[step-fn accum data]
(loop [accum accum
data data]
...))
and/or 草率地使用 re-use 变量名称可能有点令人困惑（尤其是对于 Clojure 或您的特定程序的新手）。
还有
如果我没有指出函数定义本身可以是一个 recur 目标（即您不需要使用 loop），那我就是失职了。考虑这个版本的阶乘：
(ns tst.demo.core
(:use demo.core tupelo.core tupelo.test))
(defn fact-impl
[cum x]
(if (= x 1)
cum
(let [cum-next (* cum x)
x-next (dec x)]
(recur cum-next x-next))))
(defn fact [x] (fact-impl 1 x))
(dotest
(is= 6 (fact 3))
(is= 120 (fact 5)))
评价1
首先让我们想象一下这个问题。 my-comp 如问题中所写，将创建一个函数调用的深层堆栈，每个函数调用都在堆栈上等待解析，阻塞直到最深的调用 returns -
((my-comp inc inc inc) 1)
((fn [& args]
(inc (apply (apply my-comp '(inc inc)) args))) 1)
(inc (apply (fn [& args]
(inc (apply (apply my-comp '(inc)) args))) '(1)))
(inc (inc (apply (apply my-comp '(inc)) '(1))))
(inc (inc (apply (fn [& args]
(apply inc args)) '(1))))
(inc (inc (apply inc '(1)))) ; ⚠️ deep in the hole we go...
(inc (inc 2))
(inc 3)
4
tail-recursive my-comp
此 my-comp 不是创建一长串函数，而是重构为 return 一个 单个 函数，调用时运行 loop 在提供的输入函数上 -
(defn my-comp [& fs]
(fn [init]
(loop [acc init [f & more] fs]
(if (nil? f)
acc
(recur (f acc) more))))) ; tail recursion
((my-comp inc inc inc) 1)
;; 4
((apply my-comp (repeat 1000000 inc)) 1)
;; 1000001
评价2
将my-comp重写为使用loop和recur，我们可以看到线性迭代组合的评估-
((my-comp inc inc inc) 1)
(loop 1 (list inc inc inc))
(loop 2 (list inc inc))
(loop 3 (list inc))
(loop 4 nil)
4
多个输入参数
您是否注意到此 post 开头的十 (10) 个 apply 调用？这一切都是为了支持 my-comp 序列中第一个函数的多个参数。将这种复杂性与 my-comp 本身纠缠在一起是错误的。如果这是所需的行为，调用者可以控制它。
没有对重构的任何其他更改 my-comp -
((my-comp #(apply * %) inc inc inc) '(3 4)) ; ✅ multiple input args
计算为 -
(loop '(3 4) (list #(apply * %) inc inc inc))
(loop 12 (list inc inc inc))
(loop 13 (list inc inc))
(loop 14 (list inc))
(loop 15 nil)
15
right-to-left订单
以上(my-comp a b c)会先申请a，然后b，最后c。如果您想颠倒该顺序，一个天真的解决方案是在 loop 调用站点调用 reverse -
(defn my-comp [& fs]
(fn [init]
(loop [acc init [f & more] (reverse fs)] ; ⚠️ naive
(if (nil? f)
acc
(recur (f acc) more)))))
每次调用 returned 函数时，都会重新计算 (reverse fs)。为避免这种情况，请使用 let 绑定仅计算一次反转 -
(defn my-comp [& fs]
(let [fs (reverse fs)] ; ✅ reverse once
(fn [init]
(loop [acc init [f & more] fs]
(if (nil? f)
acc
(recur (f acc) more))))))
考虑 Clojure 中 comp 的这个简单的递归实现：
(defn my-comp
([f]
(fn [& args]
(apply f args)))
([f & funcs]
(fn [& args]
(f (apply (apply my-comp funcs) args)))))
有人告诉我，正确的方法是使用 recur，但我不确定 recur 是如何工作的。特别是：有没有办法让上面的代码成为 recurable?
一种方法是重新安排此代码以将一些中间函数传递回 recur 的定义。
模型应该是这样的：
(my-comp #(* 10 %) - +)
(my-comp (fn [& args] (#(* 10 %) (apply - args)))
+)
(my-comp (fn [& args]
((fn [& args] (#(* 10 %) (apply - args)))
(apply + args))))
最后一个 my-comp 将使用第一个 my-comp 重载（即 (my-comp [f])
它可能是这样的：
(defn my-comp
([f] f)
([f & funcs]
(if (seq funcs)
(recur (fn [& args]
(f (apply (first funcs) args)))
(rest funcs))
(my-comp f))))
请注意，尽管不是可能的 apply 目标，recur 形式仍然可以接受作为序列传递的可变参数。
user> ((my-comp (partial repeat 3) #(* 10 %) - +) 1 2 3)
;;=> (-60 -60 -60)
请注意，实际上这个实现并不比你的好：虽然 recur 使你免于函数创建时的堆栈溢出，但它仍然会在应用程序中溢出（有人，请纠正我，如果我我错了）：
(apply my-comp (repeat 1000000 inc)) ;; ok
((apply my-comp (repeat 1000000 inc)) 1) ;; stack overflow
所以使用 reduce 或其他东西可能会更好：
(defn my-comp-reduce [f & fs]
(let [[f & fs] (reverse (cons f fs))]
(fn [& args]
(reduce (fn [acc curr-f] (curr-f acc))
(apply f args)
fs))))
user> ((my-comp-reduce (partial repeat 3) #(* 10 %) - +) 1 2 3)
;;=> (-60 -60 -60)
user> ((apply my-comp-reduce (repeat 1000000 inc)) 1)
;;=> 1000001
上面已经有很好的答案了，不过我觉得当初建议用recur可能是想着更加手动的积累结果。如果您还没有看到它，reduce 只是 loop/recur:
(ns tst.demo.core
(:use demo.core tupelo.core tupelo.test))
(defn my-reduce
[step-fn init-val data-vec]
(loop [accum init-val
data data-vec]
(if (empty? data)
accum
(let [accum-next (step-fn accum (first data))
data-next (rest data)]
(recur accum-next data-next)))))
(dotest
(is= 10 (my-reduce + 0 (range 5))) ; 0..4
(is= 120 (my-reduce * 1 (range 1 6))) ; 1..5 )
一般来说，可以有任意数量的循环变量（不像reduce 那样只有2 个）。使用 loop/recur 为您提供了一种更“实用”的方式来循环累积状态，而不是使用 and atom 和 doseq 或其他东西。顾名思义，从外部看，效果与普通递归非常相似 w/o 任何堆栈大小限制（即 tail-call 优化）。
P.S. 正如这个例子所示，我喜欢使用 let 形式来非常明确地命名为下一次迭代生成的值。
P.P.S. 而编译器会让你输入以下w/o混淆：
(ns tst.demo.core
(:use demo.core tupelo.core tupelo.test))
(defn my-reduce
[step-fn accum data]
(loop [accum accum
data data]
...))
and/or 草率地使用 re-use 变量名称可能有点令人困惑（尤其是对于 Clojure 或您的特定程序的新手）。
还有
如果我没有指出函数定义本身可以是一个 recur 目标（即您不需要使用 loop），那我就是失职了。考虑这个版本的阶乘：
(ns tst.demo.core
(:use demo.core tupelo.core tupelo.test))
(defn fact-impl
[cum x]
(if (= x 1)
cum
(let [cum-next (* cum x)
x-next (dec x)]
(recur cum-next x-next))))
(defn fact [x] (fact-impl 1 x))
(dotest
(is= 6 (fact 3))
(is= 120 (fact 5)))
评价1
首先让我们想象一下这个问题。 my-comp 如问题中所写，将创建一个函数调用的深层堆栈，每个函数调用都在堆栈上等待解析，阻塞直到最深的调用 returns -
((my-comp inc inc inc) 1)
((fn [& args]
(inc (apply (apply my-comp '(inc inc)) args))) 1)
(inc (apply (fn [& args]
(inc (apply (apply my-comp '(inc)) args))) '(1)))
(inc (inc (apply (apply my-comp '(inc)) '(1))))
(inc (inc (apply (fn [& args]
(apply inc args)) '(1))))
(inc (inc (apply inc '(1)))) ; ⚠️ deep in the hole we go...
(inc (inc 2))
(inc 3)
4
tail-recursive my-comp
此 my-comp 不是创建一长串函数，而是重构为 return 一个 单个 函数，调用时运行 loop 在提供的输入函数上 -
(defn my-comp [& fs]
(fn [init]
(loop [acc init [f & more] fs]
(if (nil? f)
acc
(recur (f acc) more))))) ; tail recursion
((my-comp inc inc inc) 1)
;; 4
((apply my-comp (repeat 1000000 inc)) 1)
;; 1000001
评价2
将my-comp重写为使用loop和recur，我们可以看到线性迭代组合的评估-
((my-comp inc inc inc) 1)
(loop 1 (list inc inc inc))
(loop 2 (list inc inc))
(loop 3 (list inc))
(loop 4 nil)
4
多个输入参数
您是否注意到此 post 开头的十 (10) 个 apply 调用？这一切都是为了支持 my-comp 序列中第一个函数的多个参数。将这种复杂性与 my-comp 本身纠缠在一起是错误的。如果这是所需的行为，调用者可以控制它。
没有对重构的任何其他更改 my-comp -
((my-comp #(apply * %) inc inc inc) '(3 4)) ; ✅ multiple input args
计算为 -
(loop '(3 4) (list #(apply * %) inc inc inc))
(loop 12 (list inc inc inc))
(loop 13 (list inc inc))
(loop 14 (list inc))
(loop 15 nil)
15
right-to-left订单
以上(my-comp a b c)会先申请a，然后b，最后c。如果您想颠倒该顺序，一个天真的解决方案是在 loop 调用站点调用 reverse -
(defn my-comp [& fs]
(fn [init]
(loop [acc init [f & more] (reverse fs)] ; ⚠️ naive
(if (nil? f)
acc
(recur (f acc) more)))))
每次调用 returned 函数时，都会重新计算 (reverse fs)。为避免这种情况，请使用 let 绑定仅计算一次反转 -
(defn my-comp [& fs]
(let [fs (reverse fs)] ; ✅ reverse once
(fn [init]
(loop [acc init [f & more] fs]
(if (nil? f)
acc
(recur (f acc) more))))))