真正无序的可折叠包

Question

我想要一个袋子容器,它隐藏了客户的"真实"订单.

它也必须是完全多态的,不应该对其元素类型有任何约束.

我发现了至少三种袋子的实现:Bag来自ghc包装,Data.Bag来自bag和Math.Combinatorics.Multiset来自的模块multiset-comb.

然而,它们都具有暴露元件内部顺序的操作toList和fold*操作,这可能取决于实现细节或袋构造的顺序.

toList是不可能的,至少是类型Bag a -> [a].但是,折叠并不总是暴露订单.

例如,fold (+) 0不公开.

问题是,我应该如何设计折叠界面？是否有必要和充分的a -> a -> a折叠功能安全条件？由于fmap没有暴露订单,折叠时a -> b -> b是否会失去通用性？

我正在考虑可交换的幺半群 - 它们似乎已经足够了,但我不确定是否有必要使用关联性和身份元素.

Answer 1

如果您的行李可能是空的,则可能需要身份证明 - 在这种情况下您必须返回一些东西,并且如果您希望您的折叠是同态的(因此将折叠某些行李的结果与折叠行李的结果相同)结合袋子,这是一个非常自然的特性,它必须是一个标识元素.

同样,相关性也是一个好主意.假设我有一个类型和操作,如下所示:

data T a = Zero | One a | Two (T a) (T a)
  deriving (Eq, Ord, Show)

(+-+) :: Ord a => T a -> T a -> T a
Zero +-+ x = x
x +-+ Zero = x
a +-+ b = Two (min a b) (max a b)

显然(+-+)是可交换的并且具有身份,但是是非关联的.假设我然后将一个包作为列表实现:

newtype Bag a = Bag [a]

-- pre-condition: f is commutative and z is an identity for it
foldBag :: (a -> a -> a) -> a -> Bag a -> a
foldBag f z (Bag xs) = foldr f z xs

foldNonAssoc :: (Ord a) => Bag (T a) -> T a
foldNonAssoc = foldBag (+-+) Zero

即使我要求所述的前提条件,我仍然可以使用我foldNonAssoc来区分Bag [One 1,One 2,One 3],它将折叠到Two (One 1) (Two (One 2) (One 3))和Bag [One 3,One 2,One 1]将折叠到Two (One 3) (Two (One 1) (One 2))(注意并非所有结构都被保留,但在很长的列表中我会得到整个列表除了最后两个元素的排序之外的顺序.

先验地,如果您将所有项目与操作组合在一起,您将拥有一个应用程序树,例如a +-+ (b +-+ (c +-+ d)).交换性会让你做一些重新安排,但无论你做什么,c都会一直与之相结合d.因此,如果你想要它是相同的(a +-+ c) +-+ (b +-+ d),你也真的需要关联性.