StackOverflow при обходе карты с записью типа ключа

Question

Я новичок в F #.Следовательно, возможно я что-то здесь упускаю.Однако выполнение следующего фрагмента приводит к исключению StackOverflowException:

type Node = { 
    Position: int*int
    mutable North: Node option 
    mutable South: Node option 
    mutable West:  Node option
    mutable East:  Node option }
let initialNode = { Position = 0, 0; North = None; South = None; West = None; East = None }

let second = { Position = -1, 0; North = None; South = None; West = None; East = None }
initialNode.West <- Some second
second.East <- Some initialNode
let third = { Position = -1, -1; North = None; South = None; West = None; East = None }
second.North <- Some third
third.South <- Some second
let fourth = { Position = -1, 0; North = None; South = None; West = None; East = None }
third.East <- Some fourth
fourth.West <- Some third

let distanceMap = Map.empty |> Map.add initialNode 0
let needVisit = [ initialNode ]

let newDistanceMap =
    (distanceMap, needVisit)
    ||> Seq.fold (fun map node ->
         map |> Map.add node 1)

newDistanceMap |> Map.count

Почему?Если тип ключа карты изменяется на атрибут Position (который является Tuple) типа записи, все в порядке.Следовательно, я подозреваю, что проблема заключается в использовании записей в качестве типа ключа в целом, или проблема заключается в использовании типов записей, которые имеют mutable атрибуты.

Answer 1

Проблема напрямую не связана с изменчивостью ключа, а связана с тем, что у вас есть циклы (начальный -> второй -> начальный -> ...).Если вы закомментируете строки, которые создают циклы, это будет работать.

Как Алексей предлагает вам обойти эту проблему, настроив GetHashCode / Equality для вашего типа или изменив представление ваших данных.

На самом деле это неотъемлемое ограничение неизменяемых типов данных: вы не можете представлять цикл таким простым способом.Если вы хотите работать с такими графами в F # и избегать слишком большой изменчивости, я предлагаю вам рассмотреть другой способ представления графов, например список смежностей , для более глубокого анализа попробуйте поискать индуктивные графы.

Answer 2

Следовательно, я подозреваю, что проблема заключается в использовании записей в качестве типа ключа в целом, или проблема заключается в использовании типов записей, которые имеют изменяемые атрибуты.

Это циклы ссылок (которые, строго говоря, нене требует mutable атрибутов в самих записях).Для вычисления хеш-кода записи используются хеш-коды всех ее полей.Таким образом, чтобы вычислить хеш-код initialNode, вам нужно знать хеш-код initialNode.West, который использует second, который использует second.East, который использует initialNode, который ...и т. д. и т. д.

Я не думаю, что вы можете настроить метод записи GetHashCode(), хотя я не уверен.

Обратите внимание, что сравнение на равенство может столкнуться с той же проблемой (представьте, что перемещениеPosition до конца первым).