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标签。

我的问题是这个。我的目标是向我的学生展示一些只有使用递归才能完成的事情，而非使用循环做不到的事情。但我也知道，这里我所写的代码有很多理由是不适合实际使用的。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，您将遇到"只能从尾部位置递归"的编译时错误。正如原始问题提出者所说，“有一些递归可以做的事情，用循环是无法做到的。”或者用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 ...实现。