Самостоятельная ссылка в структуре данных - Проверка на равенство

В моей первоначальной попытке создания структуры данных с непересекающимся множеством я создал Point тип данных с parent указатель на другой Point:

data Point a = Point
  { _value  :: a
  , _parent :: Point a
  , _rank   :: Int
  }

Чтобы создать одноэлементный набор, Point создан, который имеет себя в качестве родителя (я думаю, это называется связывание узла):

makeSet' :: a -> Point a
makeSet' x = let p = Point x p 0 in p

Теперь, когда я хотел написать findSet (т.е. следуйте указателям родителей, пока не найдете Point чей родитель сам) Я столкнулся с проблемой: можно ли проверить, так ли это? Наивный Eq экземпляр, конечно, будет бесконечно зацикливаться - но можно ли написать эту проверку концептуально?

(Я в конечном итоге с помощью Maybe Point для родительского поля см. мой другой вопрос.)

Источник

4 ответа

Решение

Нет, то, что вы запрашиваете, известно в мире Haskell как ссылочная идентичность: идея, что для двух значений определенного типа вы можете проверить, являются ли они одинаковыми значениями в памяти или двумя отдельными значениями, которые оказываются абсолютно одинаковыми свойства.

Для вашего примера вы можете спросить себя, считаете ли вы следующие два значения одинаковыми или нет:

pl1 :: Point Int
pl1 = Point 0 (Point 0 pl1 1) 1

pl2 :: Point Int
pl2 = Point 0 pl2 1

Haskell считает оба значения полностью равными. Т.е. Haskell не поддерживает ссылочную идентичность. Одной из причин этого является нарушение других функций, поддерживаемых Haskell. Например, в Haskell мы всегда можем заменить ссылку на функцию реализацией этой функции, не меняя смысла (эквациональное рассуждение). Например, если мы возьмем реализацию pl2: Point 0 pl2 1 и заменить pl2 по определению получаем Point 0 (Point 0 pl2 1) 1, делая pl2определение эквивалентно pl1"S. Это показывает, что Haskell не может позволить вам наблюдать разницу между pl1 а также pl2 без нарушения свойств, вытекающих из эквациональных рассуждений.

Вы можете использовать небезопасные функции, такие как unsafePerformIO (как предложено выше), чтобы обойти отсутствие ссылочной идентичности в Haskell, но вы должны знать, что тогда вы нарушаете основные принципы Haskell и можете наблюдать странные ошибки, когда GHC начинает оптимизировать (например, вставлять) ваш код. Лучше использовать другое представление ваших данных, например, то, которое вы упомянули, используя Maybe Point значение.

Источник

Вы можете попробовать сделать это, используя StableName (или же StablePtr) а также unsafePerformIO, но это кажется худшей идеей, чем Maybe Point для этого случая.

Источник

Чтобы наблюдаемый эффект, который вас, скорее всего, заинтересовал, - равенство указателей вместо равенства значений - скорее всего, вы захотите написать свой алгоритм в ST монада. ST Монаду можно считать чем-то вроде "локально нечистого ввода-вывода, глобально чистого API", хотя, по природе Union Find, вам, вероятно, придется погрузить весь процесс поиска в нечистую часть вашего кода.

К счастью, монады все еще содержат эту примесь довольно хорошо.

Также уже есть реализация Union Find в Haskell, которая использует три метода для достижения того типа личности, который вы ищете: использование IO монада, используя IntSetс, и используя ST монада.

Источник

В Haskell данные неизменны (кроме IO a, IORef a, ST a, STRef a,..) и данные это функция. Таким образом, любые данные "синглтон"

Когда вы печатаете

data C = C {a, b :: Int}
changeCa :: C -> Int -> C
changeCa c newa = c {a = newa}

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

И последнее,

data Point a = Point {p :: Point a}

это бесконечные спискообразные данные = Point { p=Point { p=Point { p=Point { ....

Источник
Другие вопросы по тегам