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（或者更少见的是，在mapfn中调用嵌套的reduce）来完成。

Answer 2

).(Scheme的例子很方便地转换成Clojure代码，所以你的例子看起来非常好。不用递归调用“treemap”，使用loop/recur。

然而，如果您需要通过一些内置工具迭代递归嵌套的结构，请尝试使用clojure.walk [1]。它包含标准迭代原语，您不必每次都编写它们。

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

Comments

loop/recur在处理树时不会直接工作。如果从不同分支递归生成结果，并使用loop/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，Hiccup 会使用向量。Sequential 是用于列表和向量的工作方式。

option3

(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 ... 的解决方案更优。