6

我想要一个能对客户隐藏其“真实”订单的 Bag 容器。

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

我发现了至少三个包的实现：Bagmodule from ghcpackage、Data.Bagfrombag和Math.Combinatorics.Multisetfrom multiset-comb。

但是，它们都具有暴露内部元素顺序toList的fold*操作，这可能取决于实现细节或包构造的顺序。

toList是不可能的，至少对于 type Bag a -> [a]。然而，折叠并不总是暴露顺序。

例如，fold (+) 0不暴露。

问题是，我应该如何设计折叠界面？a -> a -> a折叠功能的安全是否存在充要条件？由于fmap不暴露订单，折叠是否会失去通用性a -> b -> b？

我正在考虑可交换的幺半群——它们看起来就足够了，但我不确定关联性和身份元素是否是必要的。

4

1 回答 1

6

如果您的包可以是空的，则可能需要一个身份 - 在这种情况下您必须返回一些东西，并且如果您希望您的折叠是同态（因此组合折叠一些包的结果与折叠由结合袋子，这是一个非常自然的属性），它必须是一个身份元素。

同样，关联性也是一个好主意。假设我有这样的类型和操作：

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

即使我要求规定的先决条件，我仍然可以使用 myfoldNonAssoc来区分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)，那么您也确实需要关联性。

于 2012-09-05T13:17:09.580 回答