61

最近出现了一个关于 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))

我认为很明显Sets 不应该支持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)

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

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

这不适用于AlwaysEqual（例如考虑f = unWrap）。

Eq对于我们应该尊重的类型，替代法是否是一个明智的法律？当然，我们的AlwaysEqual类型尊重其他平等法则（对称性、传递性和自反性都得到了微不足道的满足），所以替换是我们唯一可能遇到麻烦的地方。

对我来说，替代似乎是Eq班级非常理想的属性。另一方面，对最近 Reddit 讨论的一些评论包括

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

——南瓜神

“我也真的不想要替代/一致，因为我们想要等同但在某种程度上可以区分的价值观有许多合法用途。”

--sclv _

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

——爱德华克梅特

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

反对Set成为 a 的另一个论点Functor- 人们普遍认为，成为 aFunctor允许您在保留形状的同时转换“集合”的“元素”。例如，Haskell wiki 上的这句话（注意这Traversable是对 的概括Functor）

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

“Traversable是关于保持原样的结构。”

在现实世界中的 Haskell

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

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

但似乎Sets 真的应该是函子（Ord暂时忽略要求 - 我认为这是我们希望有效处理集合的人为限制，而不是任何集合的绝对要求。例如，函数集是一个完全明智的考虑。无论如何，Oleg已经展示了如何为Set不需要Ord约束的情况编写高效的 Functor 和 Monad 实例）。它们有太多好的用途（对于不存在的Monad实例也是如此）。

任何人都可以清理这个烂摊子吗？应该Set是一个Functor？如果是这样，如何处理违反函子定律的可能性？法律应该是什么Eq，它们如何与法律特别Functor是Set实例相互作用？

4

3 回答 3

30

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

恐怕这是将“形状”类比作为定义条件的情况，而不是。从数学上讲，有幂集函子这样的东西。 来自维基百科：

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

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

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

（好吧，我现在就闭嘴……）

编辑：当我在答案的顶部引用你时，我截断了以下位：

例如，Haskell wiki 上的这句话（注意这Traversable是对 的概括Functor）

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

“Traversable是关于保持原样的结构。”

我想说的是，这Traversable是一种专门 Functor的，而不是它的“概括”。Traversable关于 any （或者实际上是 about Foldable，它扩展了）的关键事实之一Traversable是它要求任何结构的元素都具有线性顺序——您可以将 anyTraversable转换为它的元素列表（使用Foldable.toList）。

另一个不太明显的事实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。

于 2013-10-05T00:37:20.370 回答
11

FunctorSet 是“只是”来自 Hask 子类别的函子（不是 a ），其中Eq“nice”（即同余、替换、成立的子类别）。如果约束类型从很久以前就存在，那么set 可能是Functor某种类型的。

于 2013-10-05T04:01:55.283 回答
2

好吧，Set 可以被视为协变函子，也可以被视为逆变函子；通常它是一个协变函子。为了让它在平等方面表现得很好，必须确保无论实现什么，它都能做到。

关于 Set.zip - 这是无稽之谈。以及 Set.head （你在 Scala 中有它）。它不应该存在。

于 2013-10-11T22:29:09.453 回答