由于拉链和 HOF，递归是一种气味（在惯用的 Clojure 中）吗？

Question

经典著作The Little Lisper (The Little Schemer) 建立在两大思想之上

你可以用递归的方式解决大部分问题（而不是使用循环）（假设你有尾调用优化）
Lisp 很棒，因为它本身很容易实现。

现在有人可能认为这适用于所有 Lispy 语言（包括 Clojure）。问题是，这本书是当时（1989 年）的人工制品，可能在我们今天拥有的 Functional Programming with Higher Order Functions (HOFs) 之前。（或者至少被认为适合本科生）。

递归的好处（至少部分）是易于遍历嵌套数据结构，如 ('a 'b ('c ('d 'e)))。

对于example：

(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 - we have a non-recursive approach to traversing nested data structures, and can traverse them as we would any lazy data structure. For example:

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

现在看来您可以使用以下任一方法解决任何嵌套列表遍历问题：

a zipper 如上，或
一个遍历结构的 zipper 和 returns 一组可以让您使用 assoc 修改结构的键。

假设：

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

我的问题是：由于拉链和 HOF，递归是一种气味（在惯用的 Clojure 中）吗？

Answer 1

Clojure 习语不鼓励显式递归，因为调用堆栈是有限的：通常深度约为 10K。修改 Halloway & Bedra 的第一个 Clojure 函数式编程的六大规则（Programming Clojure（第 89 页）），

Avoid unbounded recursion. The JVM cannot optimize recursive calls and Clojure programs that recurse without bound will blow their stack.

有一些缓解措施：

recur 处理尾递归。
惰性序列可以将深调用堆栈变成浅调用堆栈
跨越展开的数据结构。序列中的许多 HOF
map 和 filter 等库，执行此操作。

Answer 2

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

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

由于拉链和 HOF，递归是一种气味（在惯用的 Clojure 中）吗？

Is recursion a smell (in idiomatic Clojure) because of of zippers and HOFs?

recursion

idioms

clojure

zipper

higher-order-functions