Как создать двусвязный список в haskell? [Дубликат]
Двоичный поиск работает, предполагая, что середина массива содержит медианное значение в массиве. Если это не отсортировано, это предположение не имеет смысла, так как медиана может быть где угодно и разрезание массива пополам может означать, что вы отрезали номер, который вы искали.
Причина, по которой двоичный поиск делает не делать сам сорт, потому что ему не нужно ... массив уже отсортирован.
2 ответа
В 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, вы получаете доступ к «родителям» части дерева, которое вы посещаете, но само дерево не должно содержать родительские ссылки.
-
1– Vitus 30 April 2012 в 19:09
-
2– Jonny Leeds 15 January 2018 в 17:05
-
3– Dmitry 30 March 2018 в 13:44
Поскольку у вас нет (обычно) объектов OO-стиля в Haskell, странно думать о том, что данные самосознательны. Важно отметить, что вы обычно не используете агрегацию в типах данных Haskell, предпочитая композицию.
Возможно, вы захотите изучить XMonad , чтобы увидеть, соответствует ли их дизайн ваши потребности (код на удивление читается).
Вы также можете захотеть перестроить свой дизайн, чтобы вам никогда не приходилось смотреть выше вас (например, передавая детям «обратные вызовы»).
Вы также можете посмотреть, можете ли вы написать молнию для всего графика.