Как мне сделать это более идиоматичным?

Итак, вот функция, которую я перевел с другого языка (Lisp), в основном дословно. Однако мне кажется, что это не совсем правильно, что с использованием ref, if без else и т. д. Как бы вы переписали вторую функцию ниже?

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

Изменить: также не требуется, чтобы код использовал Set; оригинал просто использовал список.


f# refactoring idioms
person J Cooper    schedule 08.03.2011    source источник

Ответы (1)


arrow_upward
3
arrow_downward

В целом, я думаю, что ваше решение выглядит довольно хорошо - я думаю, что это проблема, в которой небольшая изменчивость делает выражение алгоритма более ясным. Однако вместо использования изменяемой ссылки на неизменяемый набор, который вы постоянно обновляете, может быть лучше просто использовать реализацию изменяемого набора:

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

и если вы хотите, чтобы вывод был неизменяемым набором, вы можете просто добавить |> set после последней строки.

С другой стороны, если вы хотите использовать функциональный подход, это не так уж сложно:

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
person kvb    schedule 08.03.2011
comment
Ваше второе решение довольно элегантно и, по крайней мере, для меня блестяще. Я никогда раньше не использовал рекурсию изнутри сгиба! Я пытался и не смог придумать что-то подобное. Как давно вы занимаетесь функциональным программированием из любопытства? - person J Cooper; 08.03.2011
comment
@JCooper - я играю с F # в свободное время примерно с 2007 года. Я выучил Scheme в колледже, но практически не использовал ее вне занятий. - person kvb; 08.03.2011