开发者

How do I make this more idiomatic?

开发者 https://www.devze.com 2023-02-15 16:06 出处:网络
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开发者

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
0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号