集合、函子与相等性的混淆

Question

最近在工作中讨论了集合（Sets）的话题，Scala中的集合支持zip方法，但使用该方法可能会导致bug，例如：

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，

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，有

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

对于AlwaysEqual类型并不适用（例如考虑f = unWrap）。

替换定律是否适用于我们应该尊重的Eq类型？当然，其他等式定律都被我们的AlwaysEqual类型所尊重（对称性、传递性和自反性显然得到满足），因此替换是唯一可能引起问题的地方。

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

"替换看起来比必要强，基本上等价于将类型商区分，对使用类型的每个函数都有要求。"

--godofpumpkins

"我也不希望替换/同余，因为有许多合法的值可以相等，但在某种程度上是可区分的。"

--sclv

"替换仅适用于结构相等，但没有任何东西坚持Eq是结构性的。"

--edwardkmett

这三个人在Haskell社区中都很出名，因此我不愿违背他们，并坚持要求我的Eq类型具有可替换性！

另一个反对Set作为Functor的论点是——被广泛认为Functor允许您转换“集合”的“元素”，同时保留其形状。例如，Haskell wiki上的这句话（请注意，Traversable是Functor的一般化）：

"在Foldable给您穿过结构处理元素但抛弃形状的能力时，Traversable允许您保留形状并放入新值。"

"Traversable是关于完全保留结构的。"

以及在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."

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

但是似乎Set确实应该是函子（暂不考虑Ord要求——我认为这是我们希望有效地使用集合而强加的人为限制，而不是任何集合的绝对要求。例如，函数集合是一个完全合理的事情要考虑。无论如何，Oleg已经展示如何编写既不需要Ord约束的有效Functor和Monad实例，适用于Set）。只是太多了好的使用方法（非现存Monad实例同样如此）。

有谁能澄清这一混乱？

- Chris Taylor

---

也许我错了，但我不认为Scala中的集合旨在成为函子，实际上，在Scala标准库中没有诸如Functors、Monads、Applicatives等内容，因为Odersky教授不想要它们。也许在Haskell中这些是语言必不可少的部分，但在Scala中，我认为Set只是一个Set，如果你需要Functors、Monads等，请使用Scalaz。 - user1078671

与其使用“Functor”，你可以直接理解为“支持map操作的类型集合”。这就是Functor的全部含义（当然，还包括一些规则）。 - Chris Taylor

@ChrisTaylor 我同意你的观点，但是Scala中map的概念和Haskell中的map是不同的。在Haskell中，map与Functors、Arrows以及来自CatThreory的所有数学内容有关，但在Scala中，map只是“将此addOne函数应用于每个Int”。我怀疑Scala开发人员中最大的一部分并不会从Monad和某些抽象上下文的计算流程方面考虑flatMap/bind，它只是调用函数，并从List[List[A]]生成List[A]。 - user1078671

Set的map不是Functor的map！ - tibbe

我认为我们可以说Set是一个函子，作用于对象为具有合理Eq / Ord实例的类型子范畴（这里的“合理”包括可替换性）。 - Daniel Wagner

Answer 1

另一个反对将 Set 视为 Functor 的论点是，被广泛接受的是，成为 Functor 允许您在保留形状的同时转换“集合”的“元素”。[...] 显然，任何 Set 的 Functor 实例都有可能通过减少集合中的元素来改变形状。

恐怕这是一种将“形状”类比视为定义条件的情况，而实际上不是如此。从数学上讲，存在幂集函子的概念。 来自维基百科：

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

幂集函子中的函数 P(f)（幂集函子中的 fmap f）并不保留其参数集的大小，但这仍然是一个函子。

如果你需要一个不太恰当的直观比喻，我们可以这样说：在像列表这样的结构中，每个元素都“关心”它与其他元素的关系，如果错误的函子破坏了这种关系，它会感到“冒犯”。但是集合是极限情况：一个结构，其元素对彼此漠不关心，所以你几乎无法“冒犯”它们；唯一的事情是，如果一个错误的函子将包含该元素的集合映射到不包括其“声音”的结果中。

---

编辑：我在引用你的话时截取了以下部分：

例如，Haskell维基上的这句话（请注意，Traversable是Functor的一种推广）

“Foldable让您能够浏览处理元素的结构，但抛弃形状，而Traversable允许您在保留形状的同时进行操作，例如放入新值。”

“Traversable与原始结构完全相同。”

在这里，我要说的是，Traversable是一种专门化的Functor，而不是它的“推广”。任何Traversable（或实际上是Foldable，因为Traversable扩展了Foldable）的一个关键事实是，它要求任何结构的元素具有线性顺序 - 您可以使用Foldable.toList将任何Traversable转换为其元素的列表。

关于Traversable还有一个不太明显的事实，即存在以下函数（改编自Gibbons & Oliveira，“迭代器模式的本质”）：

-- | 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为[()]的集合。由此可以轻松证明，每当您尝试reassemble一个集合时，您只会得到空集或单个元素集合。

教训是什么？Traversable在比Functor更具体、更强的意义上“保持形状”。

- Luis Casillas

---

这很有趣，但根据你的回答，“Set”也是一个“Functor”吗？

1. “Set”和幂集之间唯一的区别在于幂集不使用“Eq”，而是使用实际相等性，这是可以保证替代的。
2. “Functor”在函子定律所给出的意义上“保留形状”——它只是将函数应用于元素。正如观察到的那样，假设“Eq”具有替代性，“Set”只是一个函子。

- Blaisorblade

Answer 2

Set 是从 Hask 的一个子范畴到另一个子范畴的“函数对象”（不是一个 Functor），其中 Eq 是“良好的”约束条件（即满足等价关系、可替代性质的子范畴）。如果一开始就有约束种类（constraint kinds），那么 Set 或许会成为某种类型的 Functor。

- J. Abrahamson

---

谢谢 - 我认为这是一个很好的看待问题的方式。我倾向于过于关注从Hask到Hask的函数对象，而忘记了其他的... - Chris Taylor

至少Contravariant函子是你工具箱中不错的选择，因为它们在Haskell中有非常好的表示。尽管如此，子范畴也是很好的思考工具。 - J. Abrahamson

在我看来，如果SubstitutiveEq是一个没有操作的类型类，并且只有法则（这是我在Haskell中从未见过的东西），那么instance SubstitutiveEq e => Functor (Set e)就足够了。 - Blaisorblade

@Blaisorblade 惊喜！从7.10开始， MonadPlus是一个空的类型类（嗯，除了一些冗余操作，这些操作只是它们等效泛化的别名）只提供法律 :) - Justin L.

Answer 3

嗯，Set可以被视为一个协变函子和一个逆变函子；通常它是一个协变函子。为了使它在相等性方面行为良好，必须确保无论实现如何，都是这样的。

关于Set.zip-这是无意义的。以及Set.head(你在Scala中有它)。它不应该存在。

- Vlad Patryshev

---

如果您有一个非空集合并且想获取该集合的任意元素，无论是哪个元素，那么Set.head实际上非常有用。在只有一个元素的情况下，它就是该集合的唯一元素。当然，head这个名称并不是最恰当的。它应该被称为Set.arbitrary或其他类似的名称。 - Karol S