集,函子和Eq混淆

Question

最近关于集合的讨论出现了,在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))

我认为很明显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)

可以认为这不是map对Sets 的操作的失败,而是Eq我们定义的实例的失败,因为它不尊重替换定律,即对于EqA和B的两个实例以及映射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维基的这句话(注意这Traversable是一个概括Functor)

"在哪里Foldable让你能够通过处理元素的结构但丢掉形状,Traversable允许你在保留形状的同时做到这一点,例如,将新的值放入其中."

" Traversable是关于保持结构的原样."

在真实世界哈斯克尔

"...... [A]仿函数必须保持形状.集合的结构不应受仿函数的影响;只有它包含的值才会改变."

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

但似乎Set真的应该是仿函数(忽略Ord当下的要求 - 我认为这是我们希望有效地使用集合所强加的人为限制,而不是任何集合的绝对要求.例如,函数集是一个非常明智的事情要考虑.无论如何,Oleg 已经展示了如何编写有效的Functor和Monad实例,Set不需要Ord约束).对它们来说有太多好用(对于不存在的Monad实例也是如此).

谁能清理这个烂摊子？应该Set是Functor？如果是这样,人们如何处理违反Functor法律的可能性呢？法律应该是什么Eq,以及它们如何与法律Functor和Set特定事例相互作用？

Answer 1

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

我担心这是一种将"形状"类比作为定义条件的情况.从数学角度讲,有一个功率集仿函数. 来自维基百科:

功率集:功率集仿函数P:设置→设置将每个设置映射到其功率集,每个功能f:X→Y到地图,将U⊆X发送到其图像f(U)⊆Y.

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

如果你想要一个考虑不周的直观比喻,我们可以这样说:在一个像列表这样的结构中,每个元素都"关心"它与其他元素的关系,如果一个虚假的函子打破这种关系,它将被"冒犯" .但是一组是极限情况:一个结构的元素彼此无关紧要,所以你可以做的很少"得罪"它们; 唯一的问题是,如果一个虚假的仿函数将包含该元素的集合映射到不包含其"声音"的结果.

(好吧,我现在闭嘴......)

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

例如,关于Haskell维基的这句话(注意这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-the集,其Contents是[()].从这里可以很容易地证明,无论何时尝试reassemble一个集合,你都只会得到空集或单个集合.

课？ Traversable"保持形状"是一种非常具体,更强烈的意义Functor.

Answer 2

Set是"只是" Functor来自Hask子类别的仿函数(不是a ),其中Eq"nice"(即同义,替换,保持的子类别).如果约束种类从回来开始,那么或许设置将是Functor某种类型.