集合,函数和Eq混淆

最近有一个关于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 s不应该支持zip操作,因为这些元素没有sorting。 然而,有人提出问题是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实例的失败,因为它不尊重replace定律,即对于A和B上的两个Eq实例然后映射f : A -> B

  if x == y (on A) then fx == fy (on B) 

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

对于Eqtypes来说,替代法是一个合理的法则,我们应该尊重吗? 当然,其他的平等法则是我们的AlwaysEqual平等的types(对称性,传递性和反身性是平凡的满足),所以替代是我们唯一可以陷入困境的地方。

对我来说,替代对于Eq类似乎是一个非常理想的属性。 另一方面,关于最近的Reddit讨论的一些评论包括

“替代似乎比必要的更强大,基本上取决于types,对使用types的每个function都有要求。”

godofpumpkins

“我也不想要替代/一致,因为我们想要把许多合理的价值观用于等值,但是在某种程度上是可区分的。”

sclv

“替代只是为了结构上的平等,但没有任何东西坚持Eq是结构性的。”

edwardkmett

这三个人在Haskell社区中都是非常有名的,所以我会犹豫不决,坚持我的Eqtypes的可替代性。

另一个反对Set作为Functor论据 – 作为一个Functor可以让你在保存形状的同时转换“collection”的“元素”。 例如,Haskell wiki上的这个引用(注意TraversableFunctor一个泛化)

“在Foldable ,你可以通过结构来处理元素,但是把形状扔掉, Traversable可以让你做到这一点,同时保留形状,例如,把新的价值。

“可Traversable是关于完全保持结构”。

和现实世界中的Haskell

“…函子必须保持形状,集合的结构不应该受函子的影响,只有它包含的值才会改变。

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

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

任何人都可以清理这个混乱? 应该Set一个Functor ? 如果是这样,那么对于打破Functor法则的可能性呢? Eq的法则应该是什么?它们又是如何与特定的FunctorSet实例相互作用的?

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

恐怕这是一个把“形”类比作为定义条件的情况。 从mathangular度来说,功率集函数是这样的。 维基百科 :

功率集:功率集函数P: 集合→集合将每个集合映射到其功率集合,并且每个函数f:X→Y到将U⊆X发送到其图像f(U)⊆Y的映射。

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

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

(好的,我现在闭嘴…)


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

例如,Haskell wiki上的这个引用(注意TraversableFunctor一个泛化)

“在Foldable ,你可以通过结构来处理元素,但是把形状扔掉, Traversable可以让你做到这一点,同时保留形状,例如,把新的价值。

“可Traversable是关于完全保持结构”。

这里我要说Traversable是一种专门的 Functor ,而不是它的“泛化”。 关于任何Traversable (或者实际上关于Foldable ,哪个Traversable扩展)的关键事实之一是它要求任何结构的元素都有一个线性顺序 – 你可以把任何Traversable变成它的元素列表(带有Foldable.toList )。

关于Traversable另一个不太明显的事实是存在以下函数(改编自Gibbons&Oliveira的“迭代器模式的本质” ):

 -- | A "shape" is a Traversable structure with "no content," -- ie, () at all locations. type Shape t = t () -- | "Contents" without a shape are lists of elements. type Contents a = [a] shape :: Traversable t => ta -> Shape t shape = fmap (const ()) contents :: Traversable t => ta -> 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 (ta) 

集合的Traversable实例违反了提出的法则,因为所有非空集合将具有相同的Shape – 其Contents[()]的集合。 从这里应该很容易certificate,每当你尝试reassemble一套你只会得到空集或单身回来。

课? Traversable “保存形状”,比Functor具有的特定的,更强的意义。

Set是Hask的子类别中的一个函数(而不是Functor ),其中Eq是“好的”(即同余,replace的子类别)。 如果约束种类在后面,那么可能是某种types的Functor

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

关于Set.zip – 这是无稽之谈。 以及Set.head(你在斯卡拉)。 它不应该存在。