Ответ 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, вы получаете доступ к "родителям" части дерева, которое вы посещаете, но само дерево не должно содержать родительские ссылки.