Dfs to find visited nodes in sml

Question

What is wrong with this part of code ? I'm trying to make a function which (given a graph) returns a list with all visited nodes, but the compiler keeps saying that there are some erros. Can the code be fixed ?The succesors function is used to find all nodes that are connected to the node which is takes as a parameter. I need dfs function in order to check if the returned "visited" list has all nodes, or in other words if the graph has all nodes connected to each other with a path. -The parameter tuple is a list with tuples of form (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

Those were the errors that were printed :

      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

There were two problems in your code.

First, List.exists is defined as:

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

So List.exists node visited is incorrect as node is not a function. You should instead do something like List.exists (fn n => n = node) visited.

Second, List.foldl is defined as:

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

Here again List.foldl find_visited (node::visited) s is incorrect since find_visited is of type 'a -> 'b -> 'a.

By fixing these two issues I get the following:

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;

On a side note, it's extremely inefficient to implement visited as a list: each time you meet a node you will look at all previously visited nodes to check if it's new (List.exists). Same for your implementation of your successor relation: traversing all edges of your graph to find the successors of n will be too slow.