Fでの（擬似）巡回判別集合の作成＃

Question

私はここで小さな問題に遭遇しました。私はTortoise and Hare cycle detection algorithmと書いた。

type Node = 
    | DataNode of int * Node 
    | LastNode of int 

let next node = 
    match node with 
    |DataNode(_,n) -> n 
    |LastNode(_) -> failwith "Error" 

let findCycle(first) = 
    try 
     let rec fc slow fast = 
      match (slow,fast) with 
      | LastNode(a),LastNode(b) when a=b -> true 
      | DataNode(_,a), DataNode(_,b) when a=b -> true 
      | _ -> fc (next slow) (next <| next fast) 
     fc first <| next first 
    with 
    | _ -> false 

これは、それが偽示し

let first = DataNode(1, DataNode(2, DataNode(3, DataNode(4, LastNode(5))))) 
    findCycle(first) 

のための素晴らしい取り組んでいます。右。今サイクルでテストしようとすると、を作成することができませんループ！

let first = DataNode(1, DataNode(2, DataNode(3, DataNode(4, first)))) 

しかし、私はその種のものが必要：

明らかにこれは動作しないだろう！どのように作成するか教えていただけますか？

Answer 1

を一つの方法である：

type Node = 
    | DataNode of int * Lazy<Node> 
    | LastNode of int 

    let next node = match node with |DataNode(_,n) -> n.Value |LastNode(_) -> failwith "Error" 

    let findCycle(first) = 
     try 
      let rec fc slow fast = 
       match (slow,fast) with 
       | LastNode(a),LastNode(b) when a=b->true 
       | DataNode(a,_), DataNode(b,_) when a=b -> true 
       | _ -> fc (next slow) (next <| next fast) 
      fc first <| next first 
     with 
     | _ -> false 


    let first = DataNode(1, lazy DataNode(2, lazy DataNode(3, lazy DataNode(4, lazy LastNode(5))))) 
    printfn "%A" (findCycle(first)) 


    let rec first2 = lazy DataNode(1, lazy DataNode(2, lazy DataNode(3, lazy DataNode(4, first2)))) 
    printfn "%A" (findCycle(first2.Value)) 

Answer 2

定義したタイプでは、これを行うことはできません。問題のない代替アプローチについては、How to create a recursive data structure value in (functional) F#?を参照してください。

ブライアンのソリューションに代わる方法として、次のような何かを試してみてください：ここでは

type Node = 
| DataNode of int * NodeRec 
| LastNode of int 
and NodeRec = { node : Node } 

let rec cycle = DataNode(1, { node = 
       DataNode(2, { node = 
       DataNode(3, { node = 
       DataNode(4, { node = cycle}) }) }) }) 

Answer 3

ブライアンとKVBの両方が、私はまだ感じて、仕事の回答を掲載にもかかわらず同じことを別の方法で達成することが可能かどうかを知る必要がありました。このコードは、構造自体は周期的ではありませんが、それは外からそれのように見えるあなたのSeq <としてラップ環状構造「>

type Node<'a> = Empty | Node of 'a * Node<'a> 

let cyclic (n:Node<_>) : _ = 
    let rn = ref n 

    let rec next _ = 
    match !rn with 
    | Empty -> rn := n; next Unchecked.defaultof<_> 
    | Node(v, x) -> rn := x; v 

    Seq.initInfinite next 

let nodes = Node(1, Node(2, Node(3, Empty))) 
cyclic <| nodes |> Seq.take 40 // val it : seq<int> = seq [1; 2; 3; 1; ...] 

を与えるだろう。

それともあなたがこれを行うことができます：

//removes warning about x being recursive 
#nowarn "40" 

type Node<'a> = Empty | Node of 'a * Lazy<Node<'a>> 

let rec x = Node(1, lazy Node(2, lazy x)) 

let first = 
    match x with 
    | Node(1, Lazy(Node(2,first))) -> first.Value 
    | _ -> Empty 

Answer 4

を、あなたはどのように作成する教えてもらえますか？

あり、F＃で直接巡回値を取得するための様々なハックがある（ブライアンとKVBが示されているよう）が、私は、これはあなたが実際に何をしたいことはほとんどありませんのでご注意思います。直接循環データ構造はデバッグするブタであり、通常はパフォーマンスのために使用されるため、変更可能になりました。たとえば、巡回グラフとして表されるかもしれない

：F＃でグラフを表現する慣用の方法は、必要に応じて、頂点にハンドルからマッピングし、辞書を記憶することである

> Map[1, 2; 2, 3; 3, 4; 4, 1];; 
val it : Map<int,int> = map [(1, 2); (2, 3); (3, 4); (4, 1)] 

、エッジを別の。ヒープ内のグラフを解読しようとするのとは対照的に、参照テーブルを介して間接的な再帰をトラバースするため、このアプローチは非常に簡単にデバッグできます。しかし、GCが到達不能なサブグラフを収集したい場合、弱いハッシュマップの純粋に機能的な代替は、明らかにコンピュータサイエンスの未解決の問題です。