集合，函数和Eq混淆

2018-06-15 06:20:08

最近有关集合的讨论出现了，它们在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 s不应该支持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 s上的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

这三者在哈斯克尔社区中都非常有名，所以我会犹豫不决，并且坚持要取代我的Eq类型的可替代性！

另一个反对Set作为Functor论据 - 人们普遍认为作为Functor可以让你在保存形状的同时转换“collection”的“元素”。例如，Haskell wiki上的这个引用（注意Traversable是Functor一个泛化）

“ Foldable使您能够通过处理元素的结构，但可以抛弃形状，而Traversable允许您在保留形状的同时实现这一点，例如，添加新的值。”

“可Traversable是关于完全按原样保存结构。”

和现实世界中的Haskell

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

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

但似乎Set s真的应该是仿函数（忽略Ord要求 - 我认为这是一种人为的限制，因为我们希望使用集合有效地工作，而不是任何集合的绝对要求，例如，函数是一个非常明智的事情，无论如何，Oleg已经展示了如何为Set编写高效的Functor和Monad实例，而不需要Ord约束）。对他们来说有太多好的用途（对于不存在的Monad实例也是如此）。

任何人都可以清理这个混乱？应该Set一个Functor吗？如果是这样，那么对于打破Functor法则的可能性呢？ Eq的法则应该是什么？他们如何与Functor和Set实例的法律进行交互？

另一个反对Set作为Functor论据 - 人们普遍认为作为Functor可以让你在保存形状的同时转换“collection”的“元素”。 [...]显然，Set的任何函子实例都可以通过减少集合中元素的数量来改变形状。

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

功率集：功率集函数P： 集合→集合将每个集合映射到其功率集合，并且每个函数f：X→Y到将U⊆X发送到其图像f（U）⊆Y的映射。

函数P（f）（幂集函数中的fmap f ）不保留参数集的大小，但这仍然是函数。

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

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

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

例如，Haskell wiki上的这个引用（注意Traversable是Functor一个泛化）

“ Foldable使您能够通过处理元素的结构，但可以抛弃形状，而Traversable允许您在保留形状的同时实现这一点，例如，添加新的值。”

“可Traversable是关于完全按原样保存结构。”

这里我要说Traversable是一种专门的 Functor ，而不是它的“泛化”。关于任何Traversable （或实际上关于Foldable ，哪些Traversable扩展）的关键事实之一是它要求任何结构的元素都具有线性顺序 - 您可以将任何Traversable转换为其元素列表（使用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具有更强的意义。

Set仅仅是Hask的子类别中的一个函子（不是Functor ），其中Eq是“好的”（即同余，替换保持的子类别）。如果约束种类在回来的时候，那么可能会是某种类型的Functor 。

那么Set可以被看作是一个协变函数，并且作为一个逆变函子。通常它是一个协变函数。而且为了表现出对平等的态度，人们必须确保无论执行什么，它都会这样做。

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

链接地址: http://www.djcxy.com/p/43329.html

上一篇: Sets, Functors and Eq confusion

下一篇: What laws are the standard Haskell type classes expected to uphold?