类似于Set的数据结构,维护插入顺序？

Question

我正在寻找的属性是

• 最初保持插入顺序
• 以插入顺序横向移动
• 当然要保持每个元素都是独一无二的

但有些情况下可以忽略插入顺序,例如......

• 检索两个不同集之间的差异
• 执行联合两组消除任何重复

Java的LinkedHashSet似乎正是我所追求的,除了它不是用Haskell编写的事实.

当前和初始解决方案

最简单(也是相对低效)的解决方案是将其作为列表实现,并在需要时将其转换为集合,但我相信可能有更好的方法.

其他想法

我的第一个想法就是实现它作为Data.Set一个newtype的(Int, a)地方会被第一个元组指标进行排序,第二个指标(a)是实际值.我很快意识到这不会起作用,因为该集合将允许类型的重复a,这将破坏使用集合的整个目的.

同时维护一个列表和一组？(不)

我的另一个想法是有一个抽象的数据类型,它将维护数据的列表和集合表示,这听起来效率也不高.

概括

在Haskell中是否存在这种数据结构的下降实现？我已经看过Data.List.Ordered但它似乎只是将列操作添加到列表中,这听起来非常低效(但如果我找不到解决方案,我可能会解决这个问题).这里提出的另一个解决方案是通过手指树实现它,但如果它已经解决了问题,我宁愿不重新实现它.

Answer 1

你当然可以使用Data.Set同构的东西(Int, a),但用不同的Eq实例包装在一个newtype中:

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,并且在没有太多簿记的情况下保留了很多集合的好处.