Свойства, которые я ищу, это
- изначально поддерживает порядок вставки
- пересекающий порядок вставки
- и, конечно, утверждать, что каждый элемент уникален
Но бывают случаи, когда это нормально игнорировать порядок вставки, например...
- получить разницу между двумя разными наборами
- выполнение объединения двух наборов, исключающих любые дубликаты
Java LinkedHashSet, кажется, именно то, что мне нужно, за исключением того, что он не написан в Haskell.
текущее и начальное решение
Самое простое (и релевантно неэффективное) решение - реализовать его как список и преобразовать его в набор, когда мне это тоже нужно, но я считаю, что есть лучший способ.
другие идеи
Моя первая идея заключалась в том, чтобы реализовать его как Data.Set
newtype
of (Int, a)
, где он будет упорядочен первым индексом кортежа, а второй индекс (a
) будет фактическим значением. Я быстро понял, что это не сработает, потому что, поскольку набор позволит дублировать тип a
, который бы победил всю цель использования набора.
одновременно с сохранением списка и набора? (Нету)
Другая идея, которая у меня была, - это абстрактный тип данных, который будет поддерживать как список, так и заданное представление данных, что тоже не кажется эффективным.
резюме
Существуют ли какие-либо спускные реализации такой структуры данных в Haskell? Я видел Data.List.Ordered, но, похоже, просто добавляет заданные операции в списки, что также звучит ужасно неэффективно (но, скорее всего, что Я соглашусь, если не смогу найти решение). Другое решение, предложенное здесь, состояло в том, чтобы реализовать его с помощью пальца, но я бы предпочитают не переопределять его, если это уже решена проблема.