Нужно ли предпринимать явные действия для облегчения обмена с постоянными структурами данных?

Question

Я пришел из императивного фона и пытаюсь реализовать простую структуру данных с несвязанными наборами ("объединение-поиск"), чтобы научиться создавать и модифицировать (постоянные) структуры данных в Haskell. Цель состоит в том, чтобы иметь простую реализацию, но я также обеспокоен эффективностью, и мой вопрос связан с этим.

Сначала я создал реализацию леса с несвязным множеством с объединением по рангу и начал с определения типа данных для "точки":

data Point = Point
  { _value  :: Int
  , _parent :: Maybe Point
  , _rank   :: Int
  } deriving Show

Разобщенный набор леса IntMap с Int → Point отображения:

type DSForest = IntMap Point

empty :: DSForest
empty = I.empty

Одноэлементный набор - это просто отображение его значения x в Point со значением x, без родителя и рангом 1:

makeSet :: DSForest -> Int -> DSForest
makeSet dsf x = I.insert x (Point x Nothing 0) dsf

Теперь интересная часть - union, Эта операция изменит точку, установив другую точку в качестве ее родителя (и в некоторых случаях изменит ее ранг). В случае, когда Point S 'ранг разные, то Point просто "обновляется" (создается новая точка), чтобы родительская точка указывала на другую. В случае, когда они равны, новый Point создается с повышением его на единицу:

union :: DSForest -> Int -> Int -> DSForest
union dsf x y | x == y = dsf 
union dsf x y = 
   if _value x' == _value y'
      then dsf 
      else case compare (_rank x') (_rank y') of
                  GT -> I.insert (_value y') y'{ _parent = Just x' } dsf 
                  LT -> I.insert (_value x') x'{ _parent = Just y' } dsf 
                            -- 1) increase x's rank by one:
                  EQ -> let x''  = x'{ _rank = _rank x' + 1 } 
                            -- 2) update the value for x's rank to point to the new x:
                            dsf' = I.insert (_value x'') x'' dsf 
                            -- 3) then update y to have the new x as its parent:
                         in I.insert (_value y') y'{ _parent = Just x'' } dsf'
  where x' = dsf ! findSet dsf x
        y' = dsf ! findSet dsf y

Теперь, на мой настоящий вопрос, если в EQ вместо этого я сделал следующее:

EQ -> let dsf' = I.insert (_value x') x'{ _rank = _rank x' + 1} dsf 
       in I.insert (_value y') y'{ _parent = Just x'{ _rank = _rank x' + 1 }} dsf'

Т.е. сначала вставить новый Point х с его рангом увеличился, а затем, имея y' родитель будет новым Point х с повышенным рангом, означает ли это, что они больше не указывают на то же Point в памяти? (Имеет ли это значение? Должен ли я беспокоиться об этом при использовании / создании постоянных структур данных?)

И просто для полноты, вот findSet:

findSet :: DSForest -> Int -> Int
findSet dsf' x' = case _parent (dsf' ! x') of
                     Just (Point v _ _)  -> findSet dsf' v
                     Nothing             -> x'

(Общие комментарии об эффективности и дизайне этого кода также приветствуются.)

Answer 1

Совместное использование это вещь компилятора. Когда он распознает общие подвыражения, компилятор может выбрать для представления их обоих одним и тем же объектом в памяти. Но даже если вы используете такой переключатель компилятора (как -fno-cse), он не обязан это делать, и эти два объекта могут (и обычно при отсутствии переключателя) представляться двумя разными, хотя и одинаковыми по значению объектами в памяти. Re: ссылочная прозрачность.

OTOH, когда мы называем что-то и используем это имя дважды, мы (разумно) ожидаем, что оно будет представлять один и тот же объект в памяти. Но компилятор может решить дублировать его и использовать две отдельные копии на двух разных сайтах использования, хотя это неизвестно. Но это возможно. Re: ссылочная прозрачность.

Смотрите также:

• Как запоминается эта функция Фибоначчи?
• двухпотоковая подача для предотвращения ненужного запоминания?

---

Вот несколько примеров с функциями создания списка, взятыми из последней ссылки выше. Они полагаются на то, что компилятор ничего не дублирует, т. Е. Действительно разделяет любой именованный объект, как и ожидалось от операционной семантики лямбда-исчисления (как объяснено в nponeccop в комментариях), и не вводит никакого дополнительного совместного использования для устранения общих подвыражений:

1. Совместное использование Fixpoint комбинатор, создание цикла:

   fix f = x where x = f x

2. Комбинатор без фиксированных точек, создающий телескопическую многоступенчатую цепочку (то есть регулярную рекурсивную цепочку)

   _Y f = f (_Y f)

3. Двухступенчатая комбинация - петля и питание

   _2 f = f (fix f)

Answer 2

будет ли это означать, что они больше не указывают на одну и ту же точку в памяти?

Я не думаю, что вы должны быть обеспокоены этим, так как это всего лишь деталь реализации системы времени исполнения (RTS of Haskell) для неизменяемых значений.

Что касается другого предложения, я бы сказал, сделать функцию findSet вернуть Point сам по себе, а не ключ, поскольку это устранит поиск в union,

findSet :: DSForest -> Int -> Point
findSet dsf' x' = case _parent pt of
                     Just (Point v _ _)  -> findSet dsf' v
                     Nothing             -> pt
                  where
                      pt = (dsf' ! x')

Сделайте соответствующие изменения в union функция.

Answer 3

Первый комментарий: структура данных "несвязанное множество объединение-поиск" очень и очень трудно сделать чисто чисто функциональным способом. Если вы просто пытаетесь освоить постоянные структуры данных, я настоятельно рекомендую начать с более простых структур, таких как бинарные деревья поиска.

Теперь, чтобы увидеть одну проблему, рассмотрим функцию findSet. Это не реализует сжатие пути! То есть он не делает все узлы вдоль пути к корневой точке непосредственно к корню. Для этого вам нужно обновить все эти точки в DSForest, чтобы ваша функция возвращала (Int, DSForest) или, возможно, (Point, DSForest). Делать это в монаде, чтобы справиться со всеми путями прохождения DSForest, будет проще, чем обойти этот лес вручную.

Но теперь второй вопрос. Предположим, вы изменили findSet, как описано выше. Это все еще не будет делать то, что вы хотите. В частности, предположим, что у вас есть цепочка, где 2 - это дочерний элемент 1, 3 - это дочерний элемент 2, а 4 - дочерний элемент 3. И теперь вы выполняете findSet для 3. Это обновит точку 3, чтобы ее родитель равно 1 вместо 2. Но родительский элемент 4 по-прежнему является старой точкой 3, чей родитель равен 2. Это может не иметь большого значения, потому что похоже, что вы никогда ничего не делаете с родительской точкой, за исключением извлечения ее значения (в findSet). Но сам факт того, что вы никогда ничего не делаете с родительской точкой, кроме как вытащить ее значение, говорит мне, что это должна быть Maybe Int, а не Maybe Point.

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

Структура данных несвязанного множества не имеет этого свойства. Вместо того, чтобы всегда начинать с корня и переходить к интересующим узлам, вы начинаете с произвольных узлов и возвращаетесь к корню. Когда у вас есть неограниченные точки входа, подобные этой, часто самый простой способ справиться с этим - это обеспечить общий доступ через отдельную карту (DSForest в вашем случае), но это означает, что эта карта должна передаваться туда и обратно всюду.