Clojure中的树形递归

Question

我正在尝试将《小方案师》中的一些建议练习翻译成Clojure。想法是产生一个变体的map，它可以在嵌套列表集合上工作。

(defn treemap [f tr]
      (if (list? tr)
        (if (empty? tr)
          ()
          (cons (treemap f (first tr))
                (treemap f (rest tr))))
        (f tr)))

在我的例子中，我调用了模拟的HTML页面

(html

 (head (title "the fortune cookie institute"))
 (body
  (h1 "Welcome to the Fortune Cookie Institute")
  (p "Our fortunes are guaranteed accurate no matter what.")
  (br)
  (p "Like these")
  (ol
   (li "You will gain weight")
   (li "Taxes will rise")
   (li "Fusion power will always be 50 years away"))
  (br)
  (p "Submit your own fortunes to [email protected]!")))

在这个例子中，我使用名为SHOUT的函数调用treemap，将所有的p标签替换为h1。

我的问题是这个。我的目标是向我的学生展示，有一些可以通过递归完成的事情，而用for循环是无法完成的。但我知道我在这里写下的代码存在很多理由，不适合实际应用。在Clojure中，如何正确地在嵌套集合上进行递归操作呢？

Answer 1

在Clojure中，如何正确地在嵌套集合上进行递归操作呢？

可能是 zip —— https://clojure.github.io/clojure/clojure.zip-api.html

您可能也对 hiccup 感兴趣 —— https://github.com/weavejester/hiccup

还有Specter —— https://github.com/redplanetlabs/specter

但是，对我来说，这里真正的答案是，在实践上，你很少需要在Clojure中对嵌套集合进行递归操作。这种嵌套结构很少见，并且对其进行编辑（如有必要）通常可以用assoc-in、update-in来完成，或者更少的情况下，在map的fn中调用嵌套的reduce。

Answer 2

Scheme示例可以很好地转换到Clojure，所以你的例子看起来非常好。与其递归调用"treemap"，使用loop/recur。

但是，如果你需要使用内置工具迭代深层嵌套的结构，请尝试使用clojure.walk [1]。它包含标准迭代原语，你不必每次都编写它们。

[1] https://docs.clojure.org/clojure.walk/walk

Comments

loop/recur在处理树时不会直接起作用。如果你从不同的分支递归构造结果，并使用loop/recur，你将得到"只能从尾位置recur"编译时错误。正如OP所说，“有些递归可以实现的事情，用for循环无法实现。”或者用loop/recur。我并不是说没有递归就无法处理树，但这样做比较困难。

---

如果你在循环中维护一个堆栈并向其中推送需要稍后访问的项，应该能够使用`loop/recur`？这基本上就是递归所做的事情？

Answer 3

用这个数据

(def html
'(html (head (title "the fortune cookie institute"))
     (body
      (h1 "Welcome to the Fortune Cookie Institute")
      (p "Our fortunes are guaranteed accurate no matter what.")
      (br)
      (div (p "Like these"))
      (ol
       (li "You will gain weight")
       (li "Taxes will rise")
       (li "Fusion power will always be 50 years away"))
      (br)
      (p "Submit your own fortunes to [email protected]!"))))

选项 1：使用内置的 clojure walk

(require '[clojure.walk :refer [prewalk]])
(prewalk (fn [x] (if (= x 'p) 'h2 x)) html)

注意，walker 会继续遍历，会在列表头部以外的位置找到 'p（不符合预期）。

选项 2：使用 specter

(require  '[com.rpl.specter :refer [ALL FIRST setval recursive-path]] )
(setval [ALL (recursive-path [] RECURSE
            (cond-path
             [sequential? FIRST (pred= 'p)] FIRST
             sequential? [ALL RECURSE]))]
    'h2
    html)

这里的 specter 只会寻找列表头部位置的 'p（使用 sequential? 而不是 list?，因为你的结构非常接近 hiccup，它将使用向量。sequential 对列表和向量都适用。）

选项3

(defn shout [html]
  (if-not (sequential? html)
      html
    (if (= 'p (first html))
      (cons 'h2 (->> (rest html)
                        (map shout)))
      (map shout html))))

我认为这确实会深度递归和消耗堆栈，但 HTML 的深度并不足以造成影响。我不确定是否存在一个更好的 loop [h html] ... (recur ... 答案。