Создание (псевдо) циклических дискриминируемых союзов в F #

Question

Я столкнулся с небольшой проблемой здесь. Я написал алгоритм обнаружения цикла Черепаха и Заяц .

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

Вы не можете сделать это с вашим типом, как вы его определили.См. Как создать рекурсивное значение структуры данных в (функциональном) 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 2

Вот один из способов:

  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 3

Можете ли вы сказать мне, как его создать?

Существуют различные способы получения прямого циклического значения в F # (как показали Brian и kvb), но я бы отметил, чтоэто редко то, что вы на самом деле хотите.Непосредственно циклические структуры данных предназначены для отладки и, как правило, используются для повышения производительности, поэтому их можно изменять.

Например, ваш циклический граф может быть представлен как:

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

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

Answer 4

Несмотря на то, что Брайан и Квб опубликовали ответы, которые работают, я все же чувствовал, что мне нужно посмотреть, возможно ли добиться того же самого по-другому. Этот код даст вам циклическую структуру, обернутую в Seq <'a>

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