如何在 Clojure 中实现递归 DFS（不使用向量/堆栈）
How to implement a recursive DFS in Clojure (without using a vector / stack)
我如何在 clojure 中编写与以下 python 等价的代码，但严格使用递归进行堆栈管理（例如，不使用 loop/recur 并将矢量作为边界）？
我意识到用一个向量来维护你的路径并只是偷看/弹出是相当简单的，但我这样做是作为一种思维练习。
Python版本
def dfs(start,successors,goal,visited=set()):
if start not in visited:
visited.add(start)
for s in successors.get(start):
if goal(s):
return s
else:
res = dfs(s,successors)
if res: return res #bail early when found
return False
Clojure 版本
(defn dfs [start goal? successors visited]
(if (goal? start)
start
(when (not (contains? visited start))
(mapcat #(dfs % goal? successors (conj visited start))
(successors start)))))
由于在 Clojure 版本中迭代是由对映射的调用控制的，因此您不能像在 Python 中那样尽早退出，例如if goal(s): return s。
由于您正在使用 map 收集列表内部的递归调用，因此即使在找到目标之后，您也不得不评估每个可能的节点。只有在探索了所有节点之后，您才能得到结果。
现在，我知道我可以做这样的事情（我知道这不太好......只是想提供一个简单的例子，随时提出改进建议！）但我主要想看看是否有办法避免显式使用堆栈，并让调用堆栈像 python 版本中那样工作。
(defn dfs-non-rec [frontier goal? successors visited]
(loop [f frontier g? goal? s successors v visited]
(let [node (peek f)]
(cond ; case 1
(goal? node)
node
;case 2
(not (contains? v node))
(recur (vec (concat (pop f) (successors node))) g? s (conj v node))
;case 3
:else
(recur (pop f) g? s (conj v node))))))
我该如何处理？
编辑
对于某些提供的答案是否实际上是深度优先的，我有些困惑。混淆源于我对输入所做的假设，我本来应该在此 post 中提供的。我假设输入是一个邻接表，表示 graph，而不是 tree
(def graph {"a" ["b","c","d"],
"b" ["a","e","f"],
"c" ["x","y"],
"d" [],
"e" [],
"f" [],
"x" ["c"],
"y" ["e"]})
然后当转换为 seq 时，所遵循的顺序实际上是深度优先的 对于通过在图上调用 seq 创建的结果树 ，但是不遵循邻接表，因为图结构在转换中丢失了。
因此，如果您正在寻找从 a 开始的节点 x，我希望遍历顺序是 adcyex，而不是 abcdbaefcxy
我会像下面这样使用 the Tupelo library 进行测试：
(ns tst.demo.core
(:use tupelo.test)
(:require [tupelo.core :as t] ))
(def data [[1 2 [3]]
[[4 5] 6]
[7]])
(def search-result (atom nil))
(defn search-impl
[goal? data]
(when (= ::not-found @search-result)
(if (goal? data)
(reset! search-result data)
(when (coll? data)
(doseq [it data]
(search-impl goal? it))))))
(defn search [goal? data]
(reset! search-result ::not-found)
(search-impl goal? data)
@search-result)
(dotest
(println "1 => " (search #(= 5 %) data))
(println "2 => " (search #(and (integer? %) (even? %)) data))
(println "3 => " (search #(= [4 5] %) data))
(println "4 => " (search #(= 99 %) data)) )
结果：
1 => 5
2 => 2
3 => [4 5]
4 => :tst.demo.core/not-found
当它使您的程序更清晰 and/or 更简单时，不要害怕使用一些可变状态（在本例中为原子）。
如果你真的想隐藏原子而不是全局可见的，就这样做：
(defn search2-impl
[search2-result goal? data]
(when (= ::not-found @search2-result)
(if (goal? data)
(reset! search2-result data)
(when (coll? data)
(doseq [it data]
(search2-impl search2-result goal? it))))))
(defn search2 [goal? data]
(let [search2-result (atom ::not-found)]
(search2-impl search2-result goal? data)
@search2-result))
(dotest
(println "21 => " (search2 #(= 5 %) data))
(println "22 => " (search2 #(and (integer? %) (even? %)) data))
(println "23 => " (search2 #(= [4 5] %) data))
(println "24 => " (search2 #(= 99 %) data)))
21 => 5
22 => 2
23 => [4 5]
24 => :tst.demo.core/not-found
首先你真的不需要检查循环树，因为 clojure 的数据结构没有循环引用（除非你不使用可变状态 atoms 引用另一个原子，这是一种明显的代码味道）。简单的遍历方式可能如下所示（很多 lisp（和整体编程）书籍都引用了这种方式）：
user> (defn dfs [goal? data]
(if (goal? data)
data
(loop [data data]
(when-let [[x & xs] (seq data)]
(cond (goal? x) x
(coll? x) (recur (concat x xs))
:else (recur xs))))))
user> (dfs #{10} [1 [3 5 [7 9] [10] 11 12]])
10
user> (dfs #{100} [1 [3 5 [7 9] [10] 11 12]])
nil
此外，在 clojure 中还有更简洁（因此我猜是惯用的）方法来执行此操作。最简单的一种是使用 tree-seq:
user> (defn dfs [goal? tree]
(first (filter goal? (tree-seq coll? seq tree))))
#'user/dfs
user> (dfs #{10} [1 [3 5 [7 9] [10] 11 12]])
10
user> (dfs #{100} [1 [3 5 [7 9] [10] 11 12]])
nil
user> (dfs (every-pred number? even?) [1 [3 5 [7 9] [10] 11 12]])
10
tree-seq 是惰性的，所以它只遍历树直到找到需要的值。
另一种方法是使用 clojure 的 zippers:
user> (require '[clojure.zip :as z])
nil
user> (defn dfs [goal? tree]
(loop [curr (z/zipper coll? seq identity tree)]
(cond (z/end? curr) nil
(goal? (z/node curr)) (z/node curr)
:else (recur (z/next curr)))))
#'user/dfs
user> (dfs #{10} [1 [3 5 [7 9] [10] 11 12]])
10
user> (dfs #{100} [1 [3 5 [7 9] [10] 11 12]])
nil
user> (dfs (every-pred number? even?) [1 [3 5 [7 9] [10] 11 12]])
10
我如何在 clojure 中编写与以下 python 等价的代码，但严格使用递归进行堆栈管理（例如，不使用 loop/recur 并将矢量作为边界）？
我意识到用一个向量来维护你的路径并只是偷看/弹出是相当简单的，但我这样做是作为一种思维练习。
Python版本
def dfs(start,successors,goal,visited=set()):
if start not in visited:
visited.add(start)
for s in successors.get(start):
if goal(s):
return s
else:
res = dfs(s,successors)
if res: return res #bail early when found
return False
Clojure 版本
(defn dfs [start goal? successors visited]
(if (goal? start)
start
(when (not (contains? visited start))
(mapcat #(dfs % goal? successors (conj visited start))
(successors start)))))
由于在 Clojure 版本中迭代是由对映射的调用控制的，因此您不能像在 Python 中那样尽早退出，例如if goal(s): return s。
由于您正在使用 map 收集列表内部的递归调用，因此即使在找到目标之后，您也不得不评估每个可能的节点。只有在探索了所有节点之后，您才能得到结果。
现在，我知道我可以做这样的事情（我知道这不太好......只是想提供一个简单的例子，随时提出改进建议！）但我主要想看看是否有办法避免显式使用堆栈，并让调用堆栈像 python 版本中那样工作。
(defn dfs-non-rec [frontier goal? successors visited]
(loop [f frontier g? goal? s successors v visited]
(let [node (peek f)]
(cond ; case 1
(goal? node)
node
;case 2
(not (contains? v node))
(recur (vec (concat (pop f) (successors node))) g? s (conj v node))
;case 3
:else
(recur (pop f) g? s (conj v node))))))
我该如何处理？
编辑
对于某些提供的答案是否实际上是深度优先的，我有些困惑。混淆源于我对输入所做的假设，我本来应该在此 post 中提供的。我假设输入是一个邻接表，表示 graph，而不是 tree
(def graph {"a" ["b","c","d"],
"b" ["a","e","f"],
"c" ["x","y"],
"d" [],
"e" [],
"f" [],
"x" ["c"],
"y" ["e"]})
然后当转换为 seq 时，所遵循的顺序实际上是深度优先的 对于通过在图上调用 seq 创建的结果树 ，但是不遵循邻接表，因为图结构在转换中丢失了。
因此，如果您正在寻找从 a 开始的节点 x，我希望遍历顺序是 adcyex，而不是 abcdbaefcxy
我会像下面这样使用 the Tupelo library 进行测试：
(ns tst.demo.core
(:use tupelo.test)
(:require [tupelo.core :as t] ))
(def data [[1 2 [3]]
[[4 5] 6]
[7]])
(def search-result (atom nil))
(defn search-impl
[goal? data]
(when (= ::not-found @search-result)
(if (goal? data)
(reset! search-result data)
(when (coll? data)
(doseq [it data]
(search-impl goal? it))))))
(defn search [goal? data]
(reset! search-result ::not-found)
(search-impl goal? data)
@search-result)
(dotest
(println "1 => " (search #(= 5 %) data))
(println "2 => " (search #(and (integer? %) (even? %)) data))
(println "3 => " (search #(= [4 5] %) data))
(println "4 => " (search #(= 99 %) data)) )
结果：
1 => 5
2 => 2
3 => [4 5]
4 => :tst.demo.core/not-found
当它使您的程序更清晰 and/or 更简单时，不要害怕使用一些可变状态（在本例中为原子）。
如果你真的想隐藏原子而不是全局可见的，就这样做：
(defn search2-impl
[search2-result goal? data]
(when (= ::not-found @search2-result)
(if (goal? data)
(reset! search2-result data)
(when (coll? data)
(doseq [it data]
(search2-impl search2-result goal? it))))))
(defn search2 [goal? data]
(let [search2-result (atom ::not-found)]
(search2-impl search2-result goal? data)
@search2-result))
(dotest
(println "21 => " (search2 #(= 5 %) data))
(println "22 => " (search2 #(and (integer? %) (even? %)) data))
(println "23 => " (search2 #(= [4 5] %) data))
(println "24 => " (search2 #(= 99 %) data)))
21 => 5
22 => 2
23 => [4 5]
24 => :tst.demo.core/not-found
首先你真的不需要检查循环树，因为 clojure 的数据结构没有循环引用（除非你不使用可变状态 atoms 引用另一个原子，这是一种明显的代码味道）。简单的遍历方式可能如下所示（很多 lisp（和整体编程）书籍都引用了这种方式）：
user> (defn dfs [goal? data]
(if (goal? data)
data
(loop [data data]
(when-let [[x & xs] (seq data)]
(cond (goal? x) x
(coll? x) (recur (concat x xs))
:else (recur xs))))))
user> (dfs #{10} [1 [3 5 [7 9] [10] 11 12]])
10
user> (dfs #{100} [1 [3 5 [7 9] [10] 11 12]])
nil
此外，在 clojure 中还有更简洁（因此我猜是惯用的）方法来执行此操作。最简单的一种是使用 tree-seq:
user> (defn dfs [goal? tree]
(first (filter goal? (tree-seq coll? seq tree))))
#'user/dfs
user> (dfs #{10} [1 [3 5 [7 9] [10] 11 12]])
10
user> (dfs #{100} [1 [3 5 [7 9] [10] 11 12]])
nil
user> (dfs (every-pred number? even?) [1 [3 5 [7 9] [10] 11 12]])
10
tree-seq 是惰性的，所以它只遍历树直到找到需要的值。
另一种方法是使用 clojure 的 zippers:
user> (require '[clojure.zip :as z])
nil
user> (defn dfs [goal? tree]
(loop [curr (z/zipper coll? seq identity tree)]
(cond (z/end? curr) nil
(goal? (z/node curr)) (z/node curr)
:else (recur (z/next curr)))))
#'user/dfs
user> (dfs #{10} [1 [3 5 [7 9] [10] 11 12]])
10
user> (dfs #{100} [1 [3 5 [7 9] [10] 11 12]])
nil
user> (dfs (every-pred number? even?) [1 [3 5 [7 9] [10] 11 12]])
10