Dfs查找sml中的访问节点

Question

这部分代码有什么问题?我试图使一个函数(给定一个图)返回一个列表与所有访问节点，但编译器一直说有一些错误。代码可以固定吗?继承者函数是用来找到所有连接到作为参数的节点的节点。我需要dfs函数来检查返回的"访问过"List包含所有节点，或者换句话说，如果图中的所有节点都通过路径相互连接。-参数元组是一个元组形式为(weight,node1,node1)的列表。

fun succesors n e =
List.map (fn (_,v ,_) => v) (List.filter (fn (u,_,_) => n = u) e)

fun dfs tuples node start =
let
fun find_visited visited node =
if not (List.exists node visited) then
let
val s = (succesors node tuples)
in
List.foldl find_visited (node::visited) s
end
else visited
in
find_visited [] start
end

这些是打印出来的错误:

ask2_ml.sml:75.18-75.39 Error: operator and operand don't agree 
[equality type required]
operator domain: ''Z
operand:         'Y -> bool
in expression:
succesors node
ask2_ml.sml:77.35-77.48 Error: operator and operand don't agree 
[circularity]
operator domain: ('Z -> bool) * ('Z -> bool) list
operand:         ('Z -> bool) * 'Z list
in expression:
node :: visited
ask2_ml.sml:72.7-79.16 Error: case object and rules don't agree [tycon 
mismatch]
rule domain: _ list * (_ -> bool)
object: (_ * _) * 'Z
in expression:
(case (arg,arg)
of (visited,node) =>
if not (<exp> <exp>)
then let val <binding> in <exp> <exp> end
else visited)
ask2_ml.sml:81.3-81.24 Error: operator and operand don't agree [tycon 
mismatch]
operator domain: _ * _
operand:         'Z list
in expression:
find_visited nil
uncaught exception Error
raised at: ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27
../compiler/TopLevel/interact/evalloop.sml:44.55
../compiler/TopLevel/interact/evalloop.sml:292.17-292.20

Answer 1

你的代码有两个问题。

首先，List.exists定义为:

val exists : ('a -> bool) -> 'a list -> bool

所以List.exists node visited不正确，因为node不是a函数。您应该执行类似List.exists (fn n => n = node) visited的操作。

第二，List.foldl定义为:

val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

这里再次List.foldl find_visited (node::visited) s是不正确的，因为find_visited的类型为'a -> 'b -> 'a。

通过修复这两个问题，我得到了以下内容:

fun successors n e =
List.map (fn (_,v ,_) => v) (List.filter (fn (u,_,_) => n = u) e);
fun dfs tuples node start = let
fun find_visited (node, visited) =
if List.exists (fn n => n = node) visited
then visited
else let
val s = successors node tuples
in
List.foldl find_visited (node::visited) s
end
in
find_visited (start, [])
end;

另一方面，将visited实现为列表:每次遇到一个节点时，您将查看之前的所有节点访问节点检查它是否是新的(List.exists)。你也一样实现后继关系:遍历你找到n的后继者的图表太慢了。