依存条件付きの動的に変更されたコレクションに対する反復アルゴリズムは、機能的にどのように記述できますか？

Question

私はグラフの到達不能なノードを削除するアルゴリズムは、指定されたノードで開始しており、エッジマークの入力リストに従って：

let g = Set.ofList [ (0, false, 1); 
        (0, true, 2); 
        (1, true, 3); 
        (1, false, 4); 
        (2, true, 4); 
        (4, false, 4); ] 

let nextNode graph prev value = graph |> Seq.tryPick (function 
    | prev', value', next when prev = prev' && value = value' -> Some next 
    | _ -> None) 

let noIncoming graph node = 
      not <| Set.exists (fun (_, _, node') -> node = node') graph 

let clearEdges graph start input = 
    let graph' = ref graph 
    let current = ref (Some start) 
    input 
    |> Seq.takeWhile (fun _ -> Option.exists (noIncoming !graph') !current) 
    |> Seq.iter (fun value -> 
      let next = nextNode !graph' (!current).Value value 
      graph' := Set.filter (fun (current', _, _) -> (!current).Value <> current') !graph' 
      current := next) 
    graph' 

clearEdges g 0 [false; true] 

> val it : Set<int * bool * int> ref = 
    {contents = set [(2, true, 4); (4, false, 4)];} 

それが動作するが、私は疑います参照と私のアルゴリズムclearEdgesは醜いです、私が理解する限り、F＃ - スタイルではありません。私はそれを機能的に書こうとしましたが、おそらく私は反復アルゴリズムとコレクションメソッドの組み合わせを受け取りました。それを行うための機能的アプローチはありますか？私は醜い作業コードはコードなしよりも悪いと考えているからです。ありがとう。

Answer 1

他の人が答えやコメントで言ったように、これに答えるのが最も難しいのはコードを理解することです。それは良い説明とコメントが欠けています。

コードを理解するためにまずやったのは、タイプシグニチャを追加してから、printfnステートメントをコードに追加して、その処理を確認することでした。

それ以降は、質問のコードを理解するのがずっと簡単です。

コードを再設計するときに、小さな部品を一度に変更しようとせず、printfn出力とタイプシグネチャから学んだことに基づいてコア機能を構築しました。私は躊躇せずに、refを使って変更可能なコードから、各関数の最初から再構築された不変のグラフに切り替えました。これは、既存のデータ構造を投げ捨て、毎回新しい構造を構築するのは無駄に思えるかもしれませんが、このように考えることができます。各エッジで決定を下さなければならない関数は、各エッジにアクセスする必要があります。新しいグラフに追加するかしないかのどちらかを選択すると、それを簡単にコーディングしたり、他の人が理解しやすくなるようになります。

また、タイプシグネチャをより意味深くし、コードが何をしているかを明確にするためにタイプを追加しました。少し仕事のための大きなボーナス。

次に、関数を見て、できるだけ簡潔にコードを分かりやすくすることに重点を置いて、読みやすさと保守性に重点を置き、関数をより顕著にするようにしました。

明らかに、この回答は他の2つよりも長くなりますが、元のコードよりも機能的であり、ミューテックスはなく、最初の読み方で分かりやすく、各機能の説明をコメントしています。

これがライブラリの一部である場合は、タイプシグネチャを削除するコードと、これがオプションではない一般的なものである場合は、コードを修正する必要があります。また、別々の関数を内部関数にしてリファクタリングして、組み込みのF＃コア関数を使用するようにリファクタリングし、そのときに明瞭さの損失を補うためにコメントを追加します。私はそれがKeyNotFoundException例外をスロー可能性があり、私は私の機能を好きなので、例外を回避するためにそれを変更したときに可能totalをするList.pickを使用したが実現し、以前のバージョンで

。

私の答えを見ると、私は満足していませんでしたif not (nodeUsed graph node) then;それは単純さの真っ只中のいぼだった。だから私は機能プログラミングの古いスイス軍ナイフに頼ることにした：factoring。 Pure functionalプログラミングは、基本的に数式のように因数分解できる式で、より理論的にはterm rewritingです。 notでラインを除外できるかどうか分かりました。私はそれをもっと美しくでき、これを理解しやすくなりました。したがって、notを除外する方法はlet recの外に移動することでした。 pathToNodesであり、これは遷移のリストの代わりにノードのリストを渡すことによって行うことができる。 reduceGraph2。それが完了したら、コードは簡単になりました。

私は確信していますが、コードをもっとダウンさせることができますが、私は一般的に理解しやすいので、新しいF＃人々のためにこのような答えを残します。

namespace Workspace 

module main = 

    type Node = int 
    type Transition = bool 
    type Edge = Node * Transition * Node 
    type Path = Transition list 
    type Graph = Edge list 

    [<EntryPoint>] 
    let main argv = 

     let edge1 : Edge = (0, false, 1) 
     let edge2 : Edge = (0, true , 2) 
     let edge3 : Edge = (1, true , 3) 
     let edge4 : Edge = (1, false, 4) 
     let edge5 : Edge = (2, true , 4) 
     let edge6 : Edge = (4, false, 4) 

     let g : Graph = [edge1; edge2; edge3; edge4; edge5; edge6] 

     // Given a Node, are there any Edges to that node 
     let nodeUsed (graph : Graph) (checkNode : Node) : bool = 
      List.exists (fun (_, _, toNode) -> checkNode = toNode) graph 

     // Given a Node and a transition, what is the next node 
     // This assumes that Transition is binary 
     // so only a value will be returned instead of a list. 
     let nextNode (graph : Graph) (fromNode : Node) (transition : Transition) : Node option = 
      let rec pick (graph : Graph) (fromNode : Node) (transition : Transition) : Node option = 
       match graph with 
       | (f, c, t)::tl when (f = fromNode) && (c = transition) -> Some t 
       | hd::tl -> pick tl fromNode transition 
       | _ -> None 
      pick graph fromNode transition 

     // Given a graph and a node, remove all edges that start from that node. 
     // This builds a new graph each time, thus the graph is immutable. 
     let removeNode (graph : Graph) (node : Node) : Graph = 
      let rec removeEdges graph node newGraph = 
       match graph with 
       | hd::tl -> 
        let (f,c,t) = hd 
        if (f = node) 
        // Don't add current node to new graph 
        then removeEdges tl node newGraph 
        // Add current node to new graph 
        else removeEdges tl node ((f,c,t) :: newGraph) 
       | [] -> newGraph 
      removeEdges graph node [] 

     // or 

     // let removeNode (graph : Graph) (node : Node) : Graph = 
     //  let choiceFunction elem = 
     //   match elem with 
     //   | (f,c,t) when f = node -> None 
     //   | _ -> Some(elem) 
     //  List.choose choiceFunction graph 

     // Given a graph, a starting node, and a list of transitions (path), 
     // return a new reduced graph based on the example code in the SO question. 
     let reduceGraph (graph : Graph) (start : Node) (path : Path) : Graph = 
      let rec processTransistion graph node transitions = 
       if not (nodeUsed graph node) then 
        match transitions with 
        | (transistion :: transitions) -> 
         // Get next node before removing nodes used to get next node 
         let nextNodeResult = nextNode graph node transistion 
         match nextNodeResult with 
         | Some(nextNode) -> 
          let newGraph = removeNode graph node 
          processTransistion newGraph nextNode transitions 
         | None -> graph 
        | [] -> graph 
       else graph 
      processTransistion graph start path 

     let result = reduceGraph g 0 [false; true] 
     printfn "reduceGraph - result: %A" result 

     printf "Press any key to exit: " 
     System.Console.ReadKey() |> ignore 
     printfn "" 

     0 // return an integer exit code 

。

// Give an graph, a node and a path, 
    // convert the transition list (path) to a node list 
    let pathToNodes (graph : Graph) (start : Node) (path : Path) : (Node List) = 
     let rec visit graph node transistions acc = 
      match transistions with 
      | (transition::rest) -> 
       match (nextNode graph node transition) with 
       | Some(nextNode) -> visit graph nextNode rest (nextNode :: acc) 
       | None -> List.rev acc 
      | [] -> List.rev acc 
     visit graph start path [start] 

    // Given a graph, a starting node, and a list of transitions (path), 
    // return a new reduced graph based on the example code in the SO question. 
    // This variation does so internally by a node list instead of a transition list 
    let reduceGraph2 (graph : Graph) (start : Node) (path : Path) : Graph = 
     let rec processNodes graph nodes = 
      match nodes with 
      | (currentNode :: rest) -> processNodes (removeNode graph currentNode) rest 
      | [] -> graph 
     let nodes = pathToNodes graph start path 
     processNodes graph nodes 

Answer 2

他の人が示唆したように、あなたはおそらく参照セルを使用して再割り当てを削除し、代わりに倍または再帰を使用して、いくつかの状態を蓄積したいです。ここに私が思いついたことがあります：

let reachedNodes graph start fullPath = 
    let rec loop path acc node = 
     match path with 
     | [] -> node :: acc 
     | v :: rest -> 
      let next = 
       graph 
       |> Seq.tryPick (fun (prev, value, next) -> 
        if prev = node && value = v then Some next 
        else None) 
      match next with 
      | Some c -> loop rest (node :: acc) c 
      | None -> node :: acc 
    loop fullPath [] start 
    |> Set.ofList 

let clearEdges graph start path = 
    let reachedNodes' = reachedNodes graph start path 
    let notInReachedNodes n = Set.contains n reachedNodes' |> not 
    graph 
    |> Set.filter (fun (prev, _, next) -> notInReachedNodes prev && notInReachedNodes next) 

グラフを表すためにエッジのセットを使用しました。これにより、エッジが完全に重複するのを防ぐことができますが、それでも明らかに違法な状態が許可されます。 0は、異なるノードへの2つの出て行くtrueエッジを持つことができます。グラフを(node, value)〜nodeのマップで表現する方が良いかもしれません。これは、マップのキールックアップを利用するため、このケースのパフォーマンスを向上させることもできます。

Answer 3

この機能がやって、なぜされているもの、あなたの結果のコードに文書化してください！ clearEdgesは、ホップの固定リストを2つの中止条件で行き来し、出て行くエッジを削除するとは予想していなかったので、何が起こっているのか把握するまでにはしばらく時間がかかりました。あなたには、いくつかの型の安全性を追加し、簡単にグラフをトラバースなり、これにデータ構造、変更される可能性があり

：次に

type Node = Node of int 

let g = Map.ofList [ (Node 0, false), Node 1 
        (Node 0, true), Node 2 
        (Node 1, true), Node 3 
        (Node 1, false), Node 4 
        (Node 2, true), Node 4 
        (Node 4, false), Node 4 ] 

を、clearEdgesは次のように書くことができます：いいえで

let rec clearEdges graph node hopList = 
    if List.isEmpty hopList || Map.exists (fun _ dst -> dst = node) graph then graph 
    else let graph' = Map.filter (fun (src, _) _ -> src <> node) graph 
     match Map.tryFind (node, hopList.Head) graph with 
     | None -> graph' 
     | Some node -> clearEdges graph' node hopList.Tail 

さらなる機能が必要です。コールは​​に変わります。