Упорядоченная структура данных, которая поддерживает порядок вставки?

Java LinkedHashSet, кажется, именно то, что мне нужно, за исключением того, что он не написан в Haskell.

текущее и начальное решение

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

другие идеи

Моя первая идея заключалась в том, чтобы реализовать его как Data.Set newtype of (Int, a), где он будет упорядочен первым индексом кортежа, а второй индекс (a) будет фактическим значением. Я быстро понял, что это не сработает, потому что, поскольку набор позволит дублировать тип a, который бы победил всю цель использования набора.

одновременно с сохранением списка и набора? (Нету)

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

резюме

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

Ответы

Ответ 1

Вы можете использовать Data.Set с тем, что изоморфно (Int, a), но обернуто в newtype с другим экземпляром Eq:

newtype Entry a = Entry { unEntry :: (Int, a) } deriving (Show)

instance Eq a => Eq (Entry a) where
    (Entry (_, a)) == (Entry (_, b)) = a == b

instance Ord a => Ord (Entry a) where
    compare (Entry (_, a)) (Entry (_, b)) = compare a b

Но это не решит все ваши проблемы, если вы хотите автоматически увеличивать ваш индекс, чтобы вы могли сделать обертку вокруг (Set (Entry a), Int):

newtype IndexedSet a = IndexedSet (Set (Entry a), Int) deriving (Eq, Show)

Но это означает, что вам придется повторно реализовать Data.Set, чтобы уважать это отношение:

import qualified Data.Set as S
import Data.Set (Set)
import Data.Ord (comparing)
import Data.List (sortBy)

-- declarations from above...

null :: IndexedSet a -> Bool
null (IndexedSet (set, _)) = S.null set

-- | If you re-index on deletions then size will just be the associated index
size :: IndexedSet a -> Int
size (IndexedSet (set, _)) = S.size set

-- Remember that (0, a) == (n, a) for all n
member :: Ord a => a -> IndexedSet a -> Bool
member a (IndexedSet (set, _)) = S.member (Entry (0, a)) set

empty :: IndexedSet a
empty = IndexedSet (S.empty, 0)

-- | This function is critical, you have to make sure to increment the index
--   Might also want to consider making it strict in the i field for performance
insert :: Ord a => a -> IndexedSet a -> IndexedSet a
insert a (IndexedSet (set, i)) = IndexedSet (S.insert (Entry (i, a)) set, i + 1)

-- | Simply remove the `Entry` wrapper, sort by the indices, then strip those off
toList :: IndexedSet a -> [a]
toList (IndexedSet (set, _))
    = map snd
    $ sortBy (comparing fst)
    $ map unEntry
    $ S.toList set

Но в большинстве случаев это довольно тривиально, и вы можете добавить функциональность по мере необходимости. Единственное, что вам действительно нужно беспокоиться, - это то, что нужно делать при удалении. Вы переиндексируете все или вас просто беспокоит порядок? Если вас просто беспокоит порядок, то он просто (и size может быть оставлен неоптимальным, если на самом деле рассчитать размер базового Set), но если вы повторно проиндексируете, вы можете получить свой размер в O(1) времени. Такие решения должны решаться на основе той проблемы, которую вы пытаетесь решить.

Я бы предпочел не переопределять его, если он уже решил проблему.

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