Clojure中的树形递归

Question

我正在尝试将《The Little Schemer》中的某些练习翻译成Clojure。目标是创建一个变种的map，该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

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

但是，如果您需要使用一些内置工具来迭代深层的嵌套结构，请尝试使用 clojure.walk [1]。它带有标准的迭代原语，您不必每次都写这些原语。

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

Comments

loop/recur 在处理树时不会直接起作用。如果从不同的分支递归来构建一个结果，并使用 loop/recur，您将得到 "Can only recur from tail position" 的编译期错误。正如 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 ... 的答案。