algorithm - 在 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

您不能对您定义的类型执行此操作。请参阅How to create a recursive data structure value in (functional) F#?一些可行的替代方法。

作为 Brian 解决方案的替代方案，您可以尝试以下方法:

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}) }) }) })