我可以在clojure中功能组成的实现中使用`recur'吗？

发布于 2025-01-27 10:54:04 字数 346 浏览 2 评论 0原文

考虑到comp在clojure中的这种简单的递归实现：

(defn my-comp
  ([f]
   (fn [& args]
     (apply f args)))
  ([f & funcs]
   (fn [& args]
     (f (apply (apply my-comp funcs) args)))))

我被告知正确的方法是使用recur，但我不确定recor> recur>有效。特别是：有没有办法将上述代码哄骗到recur能够？

原文

Consider this simple-minded recursive implementation of comp in Clojure:

(defn my-comp
  ([f]
   (fn [& args]
     (apply f args)))
  ([f & funcs]
   (fn [& args]
     (f (apply (apply my-comp funcs) args)))))

The right way to do this, I am told, is using recur, but I am unsure how recur works. In particular: is there a way to coax the code above into being recurable?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一杆小烟枪 2025-02-03 10:54:04

评估1

首先让我们想象一下问题。 my-comp在问题中编写时，将创建一个深层的函数调用，每个函数呼叫都在堆栈上等待解决，直到最深的呼叫返回＆nbsp; -

((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

-comp

而不是创建较长的函数序列，而是重构的my-comp以返回a single 函数，当调用时，该函数运行a > loop在提供的输入功能上 -

(defn my-comp [& fs]

  (fn [init]

    (loop [acc init [f & more] fs]

      (if (nil? f)

          acc

          (recur (f acc) more))))) ;

evaluation 1

First let's visualize the problem. my-comp as it is written in the question will create a deep stack of function calls, each waiting on the stack to resolve, blocked until the the deepest call 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

Rather than creating a long sequence of functions, this my-comp is refactored to return a single function, which when called, runs a loop over the supplied input functions -

(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

evaluation 2

With my-comp rewritten to use loop and recur, we can see linear iterative evaluation of the composition -

((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

multiple input args

Did you notice ten (10) apply calls at the beginning of this post? This is all in service to support multiple arguments for the first function in the my-comp sequence. It is a mistake to tangle this complexity with my-comp itself. The caller has control to do this if it is the desired behavior.

Without any additional changes to the refactored my-comp -

((my-comp #(apply * %) inc inc inc) '(3 4)) ; ✅ multiple input args

Which evaluates as -

(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 order

Above (my-comp a b c) will apply a first, then b, and finally c. If you want to reverse that order, a naive solution would be to call reverse at the loop call site -

(defn my-comp [& fs]
  (fn [init]
    (loop [acc init [f & more] (reverse fs)] ; ⚠️ naive
      (if (nil? f)
          acc
          (recur (f acc) more)))))

Each time the returned function is called, (reverse fs) will be recomputed. To avoid this, use a let binding to compute the reversal just once -

(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))))))

回复收藏 0 原文

一花一树开 2025-02-03 10:54:04

做到这一点的一种方法是重新排列此代码，以将一些中间功能传递给重复出现的定义。

该模型将是这样的：

(my-comp #(* 10 %) - +)

(my-comp (fn [& args] (#(* 10 %) (apply - args)))
           +)

(my-comp (fn [& args]
             ((fn [& args] (#(* 10 %) (apply - args)))
              (apply + args))))

Overload（（my-comp [f]）

- comp

(defn my-comp
  ([f] f)
  ([f & funcs]
   (if (seq funcs)
     (recur (fn [& args]
              (f (apply (first funcs) args)))
            (rest funcs))
     (my-comp f))))

最后一个my-comp将使用第一个my 表格仍然可以接受variadic参数作为序列。

user> ((my-comp (partial repeat 3) #(* 10 %) - +) 1 2 3)
;;=> (-60 -60 -60)

作为可能的应用目标，recur 您的：recur使您免于堆栈溢出的函数创建，它仍然会在应用程序上溢出（有人，如果我错了，请纠正我）：

(apply my-comp (repeat 1000000 inc)) ;; ok

((apply my-comp (repeat 1000000 inc)) 1) ;; stack overflow

因此，使用降低可能会更好或其他东西：

(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

a way to do this, is to rearrange this code to pass some intermediate function back up to the definition with recur.

the model would be something like this:

(my-comp #(* 10 %) - +)

(my-comp (fn [& args] (#(* 10 %) (apply - args)))
           +)

(my-comp (fn [& args]
             ((fn [& args] (#(* 10 %) (apply - args)))
              (apply + args))))

the last my-comp would use the first my-comp overload (which is (my-comp [f])

here's how it could look like:

(defn my-comp
  ([f] f)
  ([f & funcs]
   (if (seq funcs)
     (recur (fn [& args]
              (f (apply (first funcs) args)))
            (rest funcs))
     (my-comp f))))

notice that despite of not being the possible apply target, the recur form can still accept variadic params being passed as a sequence.

user> ((my-comp (partial repeat 3) #(* 10 %) - +) 1 2 3)
;;=> (-60 -60 -60)

notice, though, that in practice this implementation isn't really better than yours: while recur saves you from stack overflow on function creation, it would still overflow on application (somebody, correct me if i'm wrong):

(apply my-comp (repeat 1000000 inc)) ;; ok

((apply my-comp (repeat 1000000 inc)) 1) ;; stack overflow

so it would probably be better to use reduce or something else:

(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

回复收藏 0 原文

冷月断魂刀 2025-02-03 10:54:04

上面已经有一个很好的答案，但是我认为使用recur的原始建议可能一直在考虑结果的手动积累。如果您还没有看过它，降低只是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 )

通常，可以有任何数量的循环变量（不仅仅是2个循环变量喜欢减少）。使用loop/recur为您提供了使用累积状态而不是使用和atom和doseq或其他东西的“功能性”循环方式。顾名思义，从外部，效果与任何堆栈尺寸限制（即尾尾优化）的正常递归非常相似。

ps 如本示例所示，我喜欢使用let表格非常明确地命名为下一次迭代生成的值。

pps 虽然编译器允许您键入以下混乱：

(ns tst.demo.core
  (:use demo.core tupelo.core  tupelo.test))

(defn my-reduce
  [step-fn accum data]
  (loop [accum accum
         data  data]
     ...))

重新使用变量名称可能会有些混乱和/或草率（尤其是针对新手或您的特定的人程序）。

另外，

如果我没有指出功能定义本身可以是recur target（即您不需要使用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)))

There is already a good answer above, but I think the original suggestion to use recur may have been thinking of a more manual accumulation of the result. In case you haven't seen it, reduce is just a very specific usage of 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 )

In general, there can be any number of loop variables (not just 2 like for reduce). Using loop/recur gives you a more "functional" way of looping with accumulated state instead of using and atom and a doseq or something. As the name suggests, from the outside the effect is quite similar to a normal recursion w/o any stack size limits (i.e. tail-call optimization).

P.S. As this example shows, I like to use a let form to very explicitly name the values being generated for the next iteration.

P.P.S. While the compiler will allow you to type the following w/o confusion:

(ns tst.demo.core
  (:use demo.core tupelo.core  tupelo.test))

(defn my-reduce
  [step-fn accum data]
  (loop [accum accum
         data  data]
     ...))

it can be a bit confusing and/or sloppy to re-use variable names (esp. for people new to Clojure or your particular program).

Also

I would be remiss if I didn't point out that the function definition itself can be a recur target (i.e. you don't need to use loop). Consider this version of the factorial:

(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)))

回复收藏 0 原文

~没有更多了~