Как реализовать двусвязные списки

Ответ 1

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

Например, представьте, что у вас есть список [1, 2, 3, 4, 5], который вы хотите сделать дважды связанным. Теперь представьте, как представлен список:

data DoubleList a
  = LeftEnd  a (DoubleList a)
  | Middle   a (DoubleList a) (DoubleList a)
  | RightEnd a (DoubleList a)

(для простоты я использую два разных конструктора для двух концов)

Чтобы создать список выше, вы должны сначала построить первый элемент:

let e1 = LeftEnd  1 ...

Но для построения первого элемента вам уже нужен второй элемент:

let e1 = LeftEnd  1 e2
    e2 = Middle   2 e1 ...

И для второго элемента вам нужен третий и т.д.:

let e1 = LeftEnd  1 e2
    e2 = Middle   2 e1 e3
    e3 = Middle   3 e2 e4
    e4 = Middle   4 e3 e5
    e5 = RightEnd 5 e4

Это можно сделать в Haskell из-за ленивой оценки; эта стратегия называется "связывание узла" (и вам не нужно буквально переводить все в один блок let, вы можете разделить конструкцию на функции)

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

Я бы рекомендовал вместо этого использовать Data.Sequence, который представляет собой оптимизированную реализацию последовательного хранения на основе пальца. Он поддерживает очень быструю вставку, удаление и итерацию, сохраняя при этом чисто функциональную структуру данных.

В противном случае вы можете просто использовать Zipper, но использовать их для деревьев вместо списков. Более подробную информацию о Zippers можно найти на Haskell Wiki. Молнии будут очень хорошо в этой ситуации, потому что они предлагают точную функциональность, которой вы пользуетесь: если вы посещаете дерево с помощью Zipper, вы получаете доступ к "родителям" части дерева, которое вы посещаете, но само дерево не должно содержать родительские ссылки.

Ответ 2

Поскольку у вас нет (обычно) объектов OO-стиля в Haskell, странно думать о том, что данные самосознательны. Важно отметить, что вы обычно не используете агрегацию в типах данных Haskell, предпочитая композицию.

Возможно, вы захотите изучить XMonad, чтобы узнать, соответствует ли их дизайн вашим потребностям (код на удивление читается).

Вы также можете захотеть перестроить свой дизайн, чтобы вам никогда не приходилось смотреть выше вас (например, передавая детям "обратные вызовы" ).

Вы также можете посмотреть, можете ли вы написать молнию для всего графика.