集合、函子和等式混淆 [英] Sets, Functors and Eq confusion

问题描述

最近在工作中讨论了 Sets，它在 Scala 中支持 zip 方法以及这如何导致错误，例如

A discussion came up at work recently about Sets, which in Scala support the zip method and how this can lead to bugs, e.g.

scala> val words = Set("one", "two", "three")
scala> words zip (words map (_.length))
res1: Set[(java.lang.String, Int)] = Set((one,3), (two,5))

我认为很明显 Set 不应该支持 zip 操作，因为元素没有排序.然而，有人提出问题在于 Set 并不是真正的函子，不应该有 map 方法.当然，你可以通过映射一个集合来给自己带来麻烦.现在切换到 Haskell，

I think it's pretty clear that Sets shouldn't support a zip operation, since the elements are not ordered. However, it was suggested that the problem is that Set isn't really a functor, and shouldn't have a map method. Certainly, you can get yourself into trouble by mapping over a set. Switching to Haskell now,

data AlwaysEqual a = Wrap { unWrap :: a }

instance Eq (AlwaysEqual a) where
    _ == _ = True

instance Ord (AlwaysEqual a) where
    compare _ _ = EQ

现在在 ghci

ghci> import Data.Set as Set
ghci> let nums = Set.fromList [1, 2, 3]
ghci> Set.map unWrap $ Set.map Wrap $ nums
fromList [3]
ghci> Set.map (unWrap . Wrap) nums
fromList [1, 2, 3]

所以Set不满足函子律

    fmap f . fmap g = fmap (f . g)

可以说这不是 Set 上的 map 操作失败，而是 Eq 实例失败我们定义，因为它不遵守替换律，即对于 A 和 B 上的 Eq 的两个实例以及映射 f : A ->B 然后

It can be argued that this is not a failing of the map operation on Sets, but a failing of the Eq instance that we defined, because it doesn't respect the substitution law, namely that for two instances of Eq on A and B and a mapping f : A -> B then

    if x == y (on A) then f x == f y (on B)

这不适用于 AlwaysEqual(例如考虑 f = unWrap).

which doesn't hold for AlwaysEqual (e.g. consider f = unWrap).

对于我们应该尊重的 Eq 类型，替代法则是否是合理的法则?当然，我们的 AlwaysEqual 类型遵守其他平等法则(对称性、传递性和自反性基本满足)，因此替换是我们唯一可能遇到麻烦的地方.

Is the substition law a sensible law for the Eq type that we should try to respect? Certainly, other equality laws are respected by our AlwaysEqual type (symmetry, transitivity and reflexivity are trivially satisfied) so substitution is the only place that we can get into trouble.

对我来说，替换似乎是 Eq 类的一个非常理想的属性.另一方面，对最近 Reddit 讨论的一些评论包括

To me, substition seems like a very desirable property for the Eq class. On the other hand, some comments on a recent Reddit discussion include

替换似乎比必要的强，基本上是对类型进行商数，对使用该类型的每个函数提出要求."

"Substitution seems stronger than necessary, and is basically quotienting the type, putting requirements on every function using the type."

-- 南瓜之神

我也真的不想要替换/一致，因为我们想要等价但不知何故可区分的值有许多合法用途."

"I also really don't want substitution/congruence since there are many legitimate uses for values which we want to equate but are somehow distinguishable."

-- sclv

替换仅适用于结构相等，但没有任何内容坚持 Eq 是结构性的."

"Substitution only holds for structural equality, but nothing insists Eq is structural."

-- edwardkmett

这三个在 Haskell 社区中都很有名，所以我会犹豫要不要反对它们并坚持我的 Eq 类型的可替代性！

These three are all pretty well known in the Haskell community, so I'd be hesitant to go against them and insist on substitability for my Eq types!

反对 Set 是 Functor 的另一个论点 - 人们普遍认为，作为 Functor 允许您转换收藏"，同时保留形状.例如 Haskell wiki 上的这个引用(注意 Traversable 是 Functor 的概括)

Another argument against Set being a Functor - it is widely accepted that being a Functor allows you to transform the "elements" of a "collection" while preserving the shape. For example, this quote on the Haskell wiki (note that Traversable is a generalization of Functor)

其中 Foldable 使您能够通过结构处理元素但丢弃形状，Traversable 允许您在保留形状的同时做到这一点，并且，例如，放入新值."

"Where Foldable gives you the ability to go through the structure processing the elements but throwing away the shape, Traversable allows you to do that whilst preserving the shape and, e.g., putting new values in."

Traversable 是关于完全按原样保留结构."

"Traversable is about preserving the structure exactly as-is."

在现实世界中的 Haskell

and in Real World Haskell

...[A] 函子必须保持形状.集合的结构不应受到函子的影响；只有它包含的值应该改变."

"...[A] functor must preserve shape. The structure of a collection should not be affected by a functor; only the values that it contains should change."

显然，Set 的任何函子实例都有可能通过减少集合中元素的数量来改变形状.

Clearly, any functor instance for Set has the possibility to change the shape, by reducing the number of elements in the set.

但似乎 Set 真的应该是函子(暂时忽略 Ord 要求 - 我认为这是我们渴望工作的人为限制有效地使用集合，而不是任何集合的绝对要求.例如，函数集是一个非常明智的考虑.无论如何，Oleg 已经展示了如何为不需要 Ord 约束的 Set 编写高效的 Functor 和 Monad 实例).它们有太多很好的用途(对于不存在的 Monad 实例也是如此).

But it seems as though Sets really should be functors (ignoring the Ord requirement for the moment - I see that as an artificial restriction imposed by our desire to work efficiently with sets, not an absolute requirement for any set. For example, sets of functions are a perfectly sensible thing to consider. In any case, Oleg has shown how to write efficient Functor and Monad instances for Set that don't require an Ord constraint). There are just too many nice uses for them (the same is true for the non-existant Monad instance).

谁能解决这个烂摊子?Set 应该是 Functor 吗?如果是这样，对于违反函子定律的可能性，人们会怎么做?Eq 的定律应该是什么，它们如何与 Functor 和 Set 实例的定律相互作用?

Can anyone clear up this mess? Should Set be a Functor? If so, what does one do about the potential for breaking the Functor laws? What should the laws for Eq be, and how do they interact with the laws for Functor and the Set instance in particular?

推荐答案

反对 Set 是 Functor 的另一个论点 - 人们普遍认为，作为 Functor 允许您转换收藏"，同时保留形状.[...] 显然，任何 Set 的函子实例都有可能通过减少集合中元素的数量来改变形状.

Another argument against Set being a Functor - it is widely accepted that being a Functor allows you to transform the "elements" of a "collection" while preserving the shape. [...] Clearly, any functor instance for Set has the possibility to change the shape, by reducing the number of elements in the set.

恐怕这是将形状"类比作为定义条件的情况，而实际上并非如此.从数学上讲，存在幂集函子这样的东西.来自维基百科:

I'm afraid that this is a case of taking the "shape" analogy as a defining condition when it is not. Mathematically speaking, there is such a thing as the power set functor. From Wikipedia:

幂集:幂集函子 P : Set → Set 将每个集合映射到它的幂集，每个函数 f : X → Y 映射到发送 U 的映射⊆ X 到它的图像 f(U) ⊆ Y.

Power sets: The power set functor P : Set → Set maps each set to its power set and each function f : X → Y to the map which sends U ⊆ X to its image f(U) ⊆ Y.

函数 P(f)(幂集函子中的fmap f)不保留其参数集的大小，但它仍然是一个函子.

The function P(f) (fmap f in the power set functor) does not preserve the size of its argument set, yet this is nonetheless a functor.

如果你想要一个考虑不周的直观类比，我们可以这样说:在像列表这样的结构中，每个元素关心"它与其他元素的关系，如果一个假函子打破这种关系.但集合是一种限制情况:一个结构的元素彼此无关，所以你几乎无法冒犯"它们；唯一的问题是，假函子是否将包含该元素的集合映射到不包含其声音"的结果.

If you want an ill-considered intuitive analogy, we could say this: in a structure like a list, each element "cares" about its relationship to the other elements, and would be "offended" if a false functor were to break that relationship. But a set is the limiting case: a structure whose elements are indifferent to each other, so there is very little you can do to "offend" them; the only thing is if a false functor were to map a set that contains that element to a result that doesn't include its "voice."

(好吧，我现在就闭嘴……)

(Ok, I'll shut up now...)

当我在回答的开头引用您的话时，我截断了以下部分:

I truncated the following bits when I quoted you at the top of my answer:

例如Haskell wiki上的这个引用(注意Traversable是Functor的概括)

For example, this quote on the Haskell wiki (note that Traversable is a generalization of Functor)

其中 Foldable 使您能够通过结构处理元素但丢弃形状，Traversable 允许您在保留形状的同时做到这一点，并且，例如，放入新值."

"Where Foldable gives you the ability to go through the structure processing the elements but throwing away the shape, Traversable allows you to do that whilst preserving the shape and, e.g., putting new values in."

Traversable 是关于完全按原样保留结构."

"Traversable is about preserving the structure exactly as-is."

这里我要说的是 Traversable 是一种 specialized Functor，而不是它的泛化".关于任何 Traversable(或者，实际上，关于 Foldable，Traversable 扩展)的关键事实之一是它要求任何结构具有线性顺序——您可以将任何 Traversable 转换为其元素的列表(使用 Foldable.toList).

Here's I'd remark that Traversable is a kind of specialized Functor, not a "generalization" of it. One of the key facts about any Traversable (or, actually, about Foldable, which Traversable extends) is that it requires that the elements of any structure have a linear order—you can turn any Traversable into a list of its elements (with Foldable.toList).

关于 Traversable 的另一个不太明显的事实是存在以下函数(改编自 Gibbons & Oliveira，迭代器模式的本质"):

Another, less obvious fact about Traversable is that the following functions exist (adapted from Gibbons & Oliveira, "The Essence of the Iterator Pattern"):

-- | A "shape" is a Traversable structure with "no content," 
-- i.e., () at all locations.
type Shape t = t ()

-- | "Contents" without a shape are lists of elements.
type Contents a = [a]

shape :: Traversable t => t a -> Shape t
shape = fmap (const ())

contents :: Traversable t => t a -> Contents a
contents = Foldable.toList

-- | This function reconstructs any Traversable from its Shape and
-- Contents.  Law:
--
-- > reassemble (shape xs) (contents xs) == Just xs
--
-- See Gibbons & Oliveira for implementation.  Or do it as an exercise.
-- Hint: use the State monad...
--
reassemble :: Traversable t => Shape t -> Contents a -> Maybe (t a)

集合的 Traversable 实例将违反提议的法律，因为所有非空集合都将具有相同的 Shape——Contents 的集合> 是 [()].由此应该很容易证明，每当您尝试重新组合一个集合时，您只会得到空集合或单例.

A Traversable instance for sets would violate the proposed law, because all non-empty sets would have the same Shape—the set whose Contents is [()]. From this it should be easy to prove that whenever you try to reassemble a set you would only ever get the empty set or a singleton back.

课程?Traversable 在非常具体、比 Functor 更强的意义上保持形状".

Lesson? Traversable "preserves shape" in a very specific, stronger sense than Functor does.

这篇关于集合、函子和等式混淆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！