集合、函子与方程混淆

Question

最近在工作中出现了一个关于Sets的讨论，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不应该支持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)

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

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

--godofpumpkins

“我也真的不想要替换/同余，因为我们想要等同的值有很多合法的用法，但却是可以区别的。”

反对集是函子的另一个论点--人们普遍认为，作为函子允许您在保留形状的同时转换“集合”的“元素”。例如，Haskell wiki上的这段引语（注意，traversable是functor)的泛化）

“foldable使您能够通过处理元素但丢弃形状的结构，而traversable则允许您在保留形状并例如放入新值的同时执行此操作。”

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

在现实世界里哈斯克尔

“...[]函子必须保持形状。集合的结构不应受函子的影响；只应更改其包含的值。”

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

Answer 1

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

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

幂集：幂集函子P：set set将每个集合映射到它的幂集，而每个函数f：X Y映射到将U X发送到它的图像f(U)Y的映射。

如果你想要一个考虑不周的直觉类比，我们可以这样说：在一个像列表这样的结构中，每个元素“关心”它与其他元素的关系，并且如果一个假函子打破了这种关系，就会被“冒犯”。但一个集合是一个限制的情况：一个结构，它的元素彼此无关紧要，所以你能做的很少去“冒犯”它们；唯一的问题是，如果一个假函子将包含该元素的集合映射到一个不包含其“语音”的结果。

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

编辑：我在回答的顶部引用你时截断了以下几位：

这里我要指出的是，traversable是一种专门的函子，而不是它的“泛化”。关于任何traversable（或者，实际上，关于foldable，traversable对其进行了扩展）的一个关键事实是，它要求任何结构的元素具有线性顺序--您可以将任何traversable转换为其元素列表（使用foldable.tolist)。

关于traversable的另一个不太明显的事实是存在以下函数（改编自Gibbons&Oliveira，“the Essensity 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)

集合的可遍历实例将违反拟议的定律，因为所有非空集合将具有相同的形状-其内容为[()]的集合。从这一点可以很容易地证明，无论何时尝试reassemble一个集合，您只会得到空集或一个单例。

教训？traversable“保留形状”的含义非常具体，比functor的含义更强。