由于拉链和HOF,递归是一种气味(在惯用的Clojure中)吗？

Question

经典着作The Little Lisper(The Little Schemer)建立在两大创意之上

1. 您可以以递归方式解决大多数问题(而不是使用循环)(假设您有尾调用优化)
2. Lisp非常棒,因为它本身很容易实现.

现在人们可能会认为这适用于所有Lispy语言(包括Clojure).麻烦的是,这本书是当时的人工制品(1989年),可能在我们今天拥有的高阶函数功能编程(HOF)之前(或者至少被认为适合本科生).

递归(至少部分)的好处是可以轻松遍历嵌套数据结构('a 'b ('c ('d 'e))).

对于例如:

(def leftmost
  (fn [l]
    (println "(leftmost " l)
    (println (non-atom? l))
    (cond
      (null? l) '()
      (non-atom? (first l)) (leftmost (first l))
      true (first l))))

现在使用Functional Zippers - 我们有一种非递归方法来遍历嵌套数据结构,并且可以像任何惰性数据结构一样遍历它们.对于例如:

(defn map-zipper [m]
  (zip/zipper 
    (fn [x] (or (map? x) (map? (nth x 1))))
    (fn [x] (seq (if (map? x) x (nth x 1))))
    (fn [x children] 
      (if (map? x) 
        (into {} children) 
        (assoc x 1 (into {} children))))
    m))

(def m {:a 3 :b {:x true :y false} :c 4})

(-> (map-zipper m) zip/down zip/right zip/node)
;;=> [:b {:y false, :x true}]

现在看来你可以解决任何嵌套列表遍历问题:

• 一个zipper如上,或
• a zipper遍历结构并返回一组键,使您可以修改结构assoc.

假设:

• 我当然假设数据结构是固定大小的,并且在遍历之前完全已知
• 我排除了流数据源方案.

我的问题是:由于拉链和HOF,递归是一种气味(在惯用的Clojure中)吗？

Answer 1

我会说，是的，如果您正在进行手动递归，您至少应该重新考虑是否需要。但我不会说拉链与此有任何关系。我对拉链的经验是，它们具有理论用途，对 Clojure 新手来说非常令人兴奋，但一旦掌握了窍门，就没有什么实际价值了，因为它们有用的情况非常罕见。

真的是因为高阶函数已经为你实现了常见的递归模式，手动递归并不常见。但是，您绝对不应该使用手动递归：这只是一个警告信号，表明您可能可以做其他事情。在我使用 Clojure 的四年中，我什至不记得我实际上需要一个拉链的情况，但我最终经常使用递归。