So here is a function I translated from another language (Lisp), mostly verbatim-ish. It doesn't smell quite right to me though, what with using ref
, if
without else
, etc. How would you rewrite开发者_如何学Go the second function below?
let directEdges node edges =
List.filter (fun (a, b) -> a = node) edges
let getConnected node edges =
let visited = ref Set.empty
let rec traverse node =
if not (Set.contains node !visited) then
visited := Set.add node !visited
directEdges node edges
|> List.iter (fun (a, b) -> traverse b)
traverse node
!visited
Edit: There's also no requirement that the code even use a Set; the original just used a list.
Overall, I think that your solution looks pretty good - I think this is the sort of problem where a bit of mutability makes the expression of the algorithm clearer. However, rather than using a mutable reference to an immutable set which you update repeatedly, it might be better to just use a mutable set implementation:
open System.Collections.Generic
let getConnected node edges =
let visited = HashSet()
let rec traverse node =
if not (visited.Contains node) then
visited.Add node
directEdges node edges
|> List.iter (fun (a,b) -> traverse b)
traverse node
visited
and if you want the output to be an immutable set, you can just add |> set
after the last line.
On the other hand, if you want to use a functional approach it's not too hard:
let getConnected node edges =
let rec traverse node visited =
if not (Set.contains node visited) then
directEdges node edges
|> List.fold (fun nodes (a, b) -> traverse b nodes) (Set.add node visited)
else
visited
traverse node Set.empty
精彩评论