6

经典著作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))))

现在有了功能拉链——我们有一种遍历嵌套数据结构的非递归方法，并且可以像遍历任何惰性数据结构一样遍历它们。例如：_

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

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

  • azipper如上，或
  • azipper遍历结构并返回一组键，可让您使用assoc.

假设：

  • 我当然假设数据结构是固定大小的，并且在遍历之前完全知道
  • 我不包括流数据源方案。

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

4

2 回答 2

5

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

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

于 2015-03-17T00:44:57.197 回答
2

Clojure 习惯用法不鼓励显式递归，因为调用堆栈是有限的：通常深度约为 10K。修改Halloway & Bedra 的Clojure 函数式编程六项规则中的第一条（Programming Clojure (p 89)），

避免无限递归。JVM 无法优化递归调用，并且无限递归的 Clojure 程序将破坏它们的堆栈。

有几种缓解方法：

  • recur处理尾递归。

  • 惰性序列可以在展开的数据结构中将深层调用堆栈转变为浅层调用堆栈。序列
    库中的许多 HOF，例如map和filter，都是这样做的。
于 2015-03-15T16:56:30.857 回答