Clojure中的树递归

Question

我正在尝试将《简易方案》中的某些练习翻译成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，您会收到"只能在尾调用位置使用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 ...答案。