haskell - 真正无序的折叠包

Question

我想要一个 Bag 容器，它可以向客户隐藏其“真实”订单。

它还必须是完全多态的，即不需要对其元素类型有任何约束。

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

但是，它们都有 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]，它将折叠到两个(一个 1)(两个(一个 2)(一个 3)) 和 袋子 [One 3,One 2,One 1]，将折叠为 两个(一 3)(二(一 1)(一 2))(请注意，并非所有结构都被保留，但在一个很长的列表中，我将获得整个列表除最后两个元素的顺序外，按顺序返回)。

先验，如果您将所有项目与操作组合起来，您将拥有一个应用程序树，类似于 a +-+ (b +-+ (c +-+ d))。交换性会让您进行一些重新排列，但无论您做什么，c 始终会与 d 组合。因此，如果您希望它与 (a +-+ c) +-+ (b +-+ d) 相同，那么您也确实需要关联性。