集合，函数和Eq混淆 [英] Sets, Functors and Eq confusion

问题描述

最近有一个关于Sets的讨论，Scala支持 zip 方法以及这可能导致bug，例如

  scala> val words = Set（one，two，three）
 scala>单词zip（单词map（_.length））
 res1：Set [（java.lang.String，Int）] = Set（（one，3），（two，5））
  

我认为很明显， Set s不应该支持 zip 操作，因为元素没有排序。但是，有人建议问题是 Set 不是一个真正的函数，并且不应该有一个 map 方法。当然，你可以通过映射到一个集合中而陷入麻烦。现在切换到Haskell，



  data AlwaysEqual a = Wrap {unWrap :: a} 
 
实例方程（AlwaysEqual a）其中
 _ == _ = True 
 
实例Ord（AlwaysEqual a）其中
比较_ _ = 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）
  

可以说这不是失败的 map 在集合上操作 s，但是 Eq 我们定义的实例，因为它不尊重替换法则，即对于A和B上的两个 Eq 实例和一个映射 f ：A - > B then

  if x == y（on A）then fx == fy（on B ）
  

不适用于 AlwaysEqual （例如，考虑 f = unwrap ）。

是否对 Eq 类型，我们应该尝试尊重？当然，我们的 AlwaysEqual 类型（对称性，传递性和反身性得到普遍满足）会尊重其他平等法，因此替代是我们唯一可能陷入困境的地方。

对我来说，对于 Eq 类来说，替换看起来像是一个非常理想的属性。另一方面，关于最近的Reddit讨论的一些评论包括

替换似乎比必要的更强大，基本上是对类型进行了标记，并使用该类型将要求放在每个函数上。

- godofpumpkins

我也不想替代/一致，因为有很多

- sclv

$ b我们希望将其等同于某些值的合法用途$ b

替代只适用于结构性平等，但没有坚持 Eq 是结构性的。

- - edwardkmett

这三个在Haskell社区都非常有名，所以我会犹豫不决反对他们，并坚持对我的 Eq 类型进行替代！

针对 Set 是 Functor 的另一个论据 - 人们普遍认为是 Functor 允许您在保留形状的同时转换集合的元素。例如，Haskell wiki上的这个引用（注意 Traversable 是一个泛化 Functor ）

其中 Foldable 可让您通过结构处理元素但丢弃形状， Traversable 可以让你做到这一点，同时保持形状，例如，把新的价值。

和in Traversable 是关于保持结构的原样。真实世界Haskell

... [A]仿函数必须保持形状，集合的结构不应受函数的影响;

显然， Set 有可能通过减少集合中元素的数量来改变形状。

但是好像 Set s真的应该是仿函数（忽略当前的 Ord ）要求 - 我认为这是一种人为的限制，因为我们希望有效地使用集合，而不是任何集合的绝对要求。例如，功能集合是一个非常合理的考虑事项。在任何情况下，Oleg 已经显示了如何编写有效的Functor和Monad实例给 Set 不需要 Ord 约束）。对于它们来说有太多好的用途（对于不存在的 Monad 实例也是如此）。

任何人都可以清除这个混乱？应该 Set 是 Functor ？如果是这样，那么对于打破Functor法则的可能性呢？对于 Eq 的法律应该是什么，以及它们如何与 Functor 和设置实例？

解决方案

code> Set 是一个 Functor - 人们普遍认为是 Functor 允许您在保存形状的同时转换集合的元素。显然，Set的任何函子实例都可以通过减少集合中元素的数量来改变形状。

恐怕这是一个把形状类比作为一个定义条件的情况，当它不是的时候。从数学角度来说，功率集仿函数就是这样的。 维基百科：

<强大的功率集：功率集函子P：集合→集合将每个集合映射到它的幂集，并且每个函数f：X→Y映射到将U⊆X发送到它的映射image f（U）⊆Y。

函数P（f）（ fmap f


如果你想要一个不恰当的直觉类比，我们可以这样说：在一个像列表这样的结构中，每个元素关心它与其他元素的关系，如果一个假函数破坏了这种关系，就会冒犯。但是一套是极限情况：一个结构的元素彼此无关，所以你很难做到冒犯它们;唯一的一点是如果一个假仿函数将包含该元素的集映射到不包含其语音的结果。

（好的，我'我现在闭嘴...）

---

编辑：引用你在我的答案的顶部：

例如，Haskell wiki上的这个引用（注意 Traversable 是 Functor 的概括）

lockquote

Where Foldable 让您可以通过处理元素的结构但丢弃形状， Traversable 允许您执行在保留形状的同时，例如，增加新的价值。

Traversable 是关于保存结构

这里我要说 Traversable 是一种专用的 Functor ，不是它的泛化。关于任何 Traversable （或者实际上，关于 Foldable ，其中 Traversable extends）是它要求任何结构的元素都有一个线性顺序 - 你可以把任何 Traversable 变成它的元素列表 Foldable.toList ）。

另一个不太明显的事实是 Traversable 是存在以下功能（根据 Gibbons& Oliveira，The Essence Iterator Pattern）：

   -  | 形状是具有无内容的可穿越结构，
  - 即（）在所有位置。 
类型形状t = t（）
 
  -  |没有形状的内容是元素列表。 
类型内容a = [a] 
 
 shape :: Traversable t => t a  - > Shape t 
 shape = fmap（const（））
 
 contents :: Traversable t => t a  - >内容a 
 contents = Foldable.toList 
 
  -  |此函数从其形状和
  - 内容重建任何Traversable。法律：
  -  
  - >重新组装（形状xs）（内容xs）==只需xs 
  -  
  - 参见Gibbons&奥利维拉实施。或者做一个练习。 
  - 提示：使用状态monad ... 
  -  
 reassemble :: Traversable t =>形状t  - >内容a  - >也许（ta）
  

一个 Traversable 因为所有非空集都具有相同的 Shape - Contents 是 [（）] 。从这里可以很容易证明，每当你尝试 reassemble 一个集合，你将只能获得空集或单例集。

课程？ Traversable 保留形状，比 Functor 具有更强的意义。

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))

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

and now in 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]

So Set fails to satisfy the functor law

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

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)

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

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.

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."

-- godofpumpkins

"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

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

-- edwardkmett

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!

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)

"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 is about preserving the structure exactly as-is."

and in Real World Haskell

"...[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."

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

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).

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?

解决方案

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:

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.

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...)

---

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

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

"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 is about preserving the structure exactly as-is."

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).

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)

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.

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

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