Clojure中的树递归

Question

我试图将《The Little Schemer》中的一些练习翻译成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)

请注意，该遍历器会继续行走，并可能在列表头部之外的位置找到'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 ...解决方案。