scala - 集合、仿函数和方程混淆

Question

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

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 then

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

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

对于我们应该尊重的 Eq 类型来说，替换定律是一个合理的定律吗？当然，我们的 AlwaysEqual 类型尊重其他平等法则(对称性、传递性和自反性都得到满足)，因此替换是我们唯一可能遇到麻烦的地方。

对我来说，替换似乎是 Eq 类非常理想的属性。另一方面，一些关于recent Reddit discussion的评论包括

"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

这三个在 Haskell 社区中都是众所周知的，所以我会犹豫是否要反对它们并坚持对我的 Eq 类型进行替代!

反对 Set 作为 Functor 的另一个论点 - 人们广泛认为，作为 Functor 允许您转换 a 的“元素” “收藏”的同时保留了形状。例如，Haskell wiki 上的这段引用(请注意，Traversable 是 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."

在现实世界的 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 has shown 如何为 Set 编写高效的 Functor 和 Monad 实例 不需要 Ord 约束)。它们有太多好的用途(对于不存在的 Monad 实例也是如此)。

有人能清理这个烂摊子吗？ Set 应该是 Functor 吗？如果是这样，那么对于违反仿函数定律的可能性，人们会采取什么措施呢？ Eq 的法则应该是什么？它们如何与 Functor 以及特别是 Set 实例的法则交互？

Answer 1

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.

恐怕这是一种以“形状”类比作为定义条件的情况，而事实并非如此。从数学上来说，有幂集仿函数这样的东西。 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.

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

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

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

<小时/>

编辑:当我在答案顶部引用您时，我截断了以下内容:

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

我要说的是Traversable是一种专门 Functor ，而不是它的“概括”。关于任何Traversable的关键事实之一(或者，实际上，关于 Foldable ， Traversable 扩展)是它要求任何结构的元素都具有线性顺序 - 您可以将任何 Traversable 转换为线性顺序。放入其元素列表中(使用 Foldable.toList )。

关于 Traversable 的另一个不太明显的事实是存在以下函数(改编自 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 的集合是 [()] 。由此应该很容易证明，每当您尝试 reassemble一个集合，您只能得到空集合或单例返回。

教训？ Traversable “保持形状”的含义比 Functor 更具体、更强烈。确实如此。