集合,函数和Eq混淆 [英] Sets, Functors and Eq confusion
问题描述
zip
方法以及这可能导致bug,例如 scala> val words = Set(one,two,three)
scala>单词zip(单词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}
实例方程(AlwaysEqual a)其中
_ == _ = True
实例Ord(AlwaysEqual a)其中
比较_ _ = 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 在
集合上操作 s,但是
我们定义的实例,因为它不尊重替换法则,即对于A和B上的两个 Eq
实例和一个映射 f :A - > B
then
if x == y(on A)then fx == fy(on B )
不适用于 AlwaysEqual
(例如,考虑 f = unwrap
)。
是否对 Eq
类型,我们应该尝试尊重?当然,我们的 AlwaysEqual
类型(对称性,传递性和反身性得到普遍满足)会尊重其他平等法,因此替代是我们唯一可能陷入困境的地方。
对我来说,对于 Eq
类来说,替换看起来像是一个非常理想的属性。另一方面,关于最近的Reddit讨论的一些评论包括
替换似乎比必要的更强大,基本上是对类型进行了标记,并使用该类型将要求放在每个函数上。
- godofpumpkins
我也不想替代/一致,因为有很多
- sclv
$ b我们希望将其等同于某些值的合法用途$ b替代只适用于结构性平等,但没有坚持
Eq
是结构性的。
- - edwardkmett
这三个在Haskell社区都非常有名,所以我会犹豫不决反对他们,并坚持对我的 Eq
类型进行替代!
针对 Set 是
的另一个论据 - 人们普遍认为是 Functor
允许您在保留形状的同时转换集合的元素。例如,Haskell wiki上的这个引用(注意 Traversable
是一个泛化 Functor
)
其中
Foldable
可让您通过结构处理元素但丢弃形状,Traversable
可以让你做到这一点,同时保持形状,例如,把新的价值。
和in Traversable
是关于保持结构的原样。真实世界Haskell
... [A]仿函数必须保持形状,集合的结构不应受函数的影响;
显然, Set $ c的任何函子实例$ c>有可能通过减少集合中元素的数量来改变形状。
但是好像 Set
s真的应该是仿函数(忽略当前的
Ord
)要求 - 我认为这是一种人为的限制,因为我们希望有效地使用集合,而不是任何集合的绝对要求。例如,功能集合是一个非常合理的考虑事项。在任何情况下,Oleg 已经显示了如何编写有效的Functor和Monad实例给 Set
不需要 Ord
约束)。对于它们来说有太多好的用途(对于不存在的 Monad
实例也是如此)。
任何人都可以清除这个混乱?应该 Set
是 Functor
?如果是这样,那么对于打破Functor法则的可能性呢?对于 Eq
的法律应该是什么,以及它们如何与 Functor
和设置
实例?
code> Set 是一个
Functor
- 人们普遍认为是Functor
允许您在保存形状的同时转换集合的元素。显然,Set的任何函子实例都可以通过减少集合中元素的数量来改变形状。
恐怕这是一个把形状类比作为一个定义条件的情况,当它不是的时候。从数学角度来说,功率集仿函数就是这样的。 维基百科:
<强大的功率集:功率集函子P:集合→集合将每个集合映射到它的幂集,并且每个函数f:X→Y映射到将U⊆X发送到它的映射image f(U)⊆Y。
函数P(f)( 如果你想要一个不恰当的直觉类比,我们可以这样说:在一个像列表这样的结构中,每个元素关心它与其他元素的关系,如果一个假函数破坏了这种关系,就会冒犯。但是一套是极限情况:一个结构的元素彼此无关,所以你很难做到冒犯它们;唯一的一点是如果一个假仿函数将包含该元素的集映射到不包含其语音的结果。 (好的,我'我现在闭嘴...) 编辑:引用你在我的答案的顶部: 例如,Haskell wiki上的这个引用(注意 Where 这里我要说 另一个不太明显的事实是 一个 fmap f $ c
一个集合,你将只能获得空集或单例集。
Traversable
是 Functor
的概括)
lockquote
Foldable
让您可以通过处理元素的结构但丢弃形状, Traversable
允许您执行在保留形状的同时,例如,增加新的价值。
Traversable
是关于保存结构
Traversable
是一种专用的 Functor
,不是它的泛化。关于任何 Traversable
(或者实际上,关于 Foldable
,其中 Traversable
extends)是它要求任何结构的元素都有一个线性顺序 - 你可以把任何 Traversable
变成它的元素列表 Foldable.toList
)。
Traversable
是存在以下功能(根据 Gibbons& Oliveira,The Essence Iterator Pattern):
- | 形状是具有无内容的可穿越结构,
- 即()在所有位置。
类型形状t = t()
- |没有形状的内容是元素列表。
类型内容a = [a]
shape :: Traversable t => t a - > Shape t
shape = fmap(const())
contents :: Traversable t => t a - >内容a
contents = Foldable.toList
- |此函数从其形状和
- 内容重建任何Traversable。法律:
-
- >重新组装(形状xs)(内容xs)==只需xs
-
- 参见Gibbons&奥利维拉实施。或者做一个练习。
- 提示:使用状态monad ...
-
reassemble :: Traversable t =>形状t - >内容a - >也许(ta)
Traversable
因为所有非空集都具有相同的 Shape
- Contents
是 [()]
。从这里可以很容易证明,每当你尝试
课程? Traversable
保留形状,比 Functor
具有更强的意义。
A discussion came up at work recently about Sets, which in Scala support the zip
method and how this can lead to bugs, e.g.
scala> val words = Set("one", "two", "three")
scala> words zip (words map (_.length))
res1: Set[(java.lang.String, Int)] = Set((one,3), (two,5))
I think it's pretty clear that Set
s shouldn't support a zip
operation, since the elements are not ordered. However, it was suggested that the problem is that Set
isn't really a functor, and shouldn't have a map
method. Certainly, you can get yourself into trouble by mapping over a set. Switching to Haskell now,
data AlwaysEqual a = Wrap { unWrap :: a }
instance Eq (AlwaysEqual a) where
_ == _ = True
instance Ord (AlwaysEqual a) where
compare _ _ = EQ
and now in 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]
So Set
fails to satisfy the functor law
fmap f . fmap g = fmap (f . g)
It can be argued that this is not a failing of the map
operation on Set
s, but a failing of the Eq
instance that we defined, because it doesn't respect the substitution law, namely that for two instances of Eq
on A and B and a mapping f : A -> B
then
if x == y (on A) then f x == f y (on B)
which doesn't hold for AlwaysEqual
(e.g. consider f = unWrap
).
Is the substition law a sensible law for the Eq
type that we should try to respect? Certainly, other equality laws are respected by our AlwaysEqual
type (symmetry, transitivity and reflexivity are trivially satisfied) so substitution is the only place that we can get into trouble.
To me, substition seems like a very desirable property for the Eq
class. On the other hand, some comments on a recent Reddit discussion include
"Substitution seems stronger than necessary, and is basically quotienting the type, putting requirements on every function using the type."
-- godofpumpkins
"I also really don't want substitution/congruence since there are many legitimate uses for values which we want to equate but are somehow distinguishable."
-- sclv
"Substitution only holds for structural equality, but nothing insists
Eq
is structural."-- edwardkmett
These three are all pretty well known in the Haskell community, so I'd be hesitant to go against them and insist on substitability for my Eq
types!
Another argument against Set
being a Functor
- it is widely accepted that being a Functor
allows you to transform the "elements" of a "collection" while preserving the shape. For example, this quote on the Haskell wiki (note that Traversable
is a generalization of Functor
)
"Where
Foldable
gives you the ability to go through the structure processing the elements but throwing away the shape,Traversable
allows you to do that whilst preserving the shape and, e.g., putting new values in.""
Traversable
is about preserving the structure exactly as-is."
and in Real World Haskell
"...[A] functor must preserve shape. The structure of a collection should not be affected by a functor; only the values that it contains should change."
Clearly, any functor instance for Set
has the possibility to change the shape, by reducing the number of elements in the set.
But it seems as though Set
s really should be functors (ignoring the Ord
requirement for the moment - I see that as an artificial restriction imposed by our desire to work efficiently with sets, not an absolute requirement for any set. For example, sets of functions are a perfectly sensible thing to consider. In any case, Oleg has shown how to write efficient Functor and Monad instances for Set
that don't require an Ord
constraint). There are just too many nice uses for them (the same is true for the non-existant Monad
instance).
Can anyone clear up this mess? Should Set
be a Functor
? If so, what does one do about the potential for breaking the Functor laws? What should the laws for Eq
be, and how do they interact with the laws for Functor
and the Set
instance in particular?
Another argument against
Set
being aFunctor
- it is widely accepted that being aFunctor
allows you to transform the "elements" of a "collection" while preserving the shape. [...] Clearly, any functor instance for Set has the possibility to change the shape, by reducing the number of elements in the set.
I'm afraid that this is a case of taking the "shape" analogy as a defining condition when it is not. Mathematically speaking, there is such a thing as the power set functor. From Wikipedia:
Power sets: The power set functor P : Set → Set maps each set to its power set and each function f : X → Y to the map which sends U ⊆ X to its image f(U) ⊆ Y.
The function P(f) (fmap f
in the power set functor) does not preserve the size of its argument set, yet this is nonetheless a functor.
If you want an ill-considered intuitive analogy, we could say this: in a structure like a list, each element "cares" about its relationship to the other elements, and would be "offended" if a false functor were to break that relationship. But a set is the limiting case: a structure whose elements are indifferent to each other, so there is very little you can do to "offend" them; the only thing is if a false functor were to map a set that contains that element to a result that doesn't include its "voice."
(Ok, I'll shut up now...)
EDIT: I truncated the following bits when I quoted you at the top of my answer:
For example, this quote on the Haskell wiki (note that
Traversable
is a generalization ofFunctor
)"Where
Foldable
gives you the ability to go through the structure processing the elements but throwing away the shape,Traversable
allows you to do that whilst preserving the shape and, e.g., putting new values in.""
Traversable
is about preserving the structure exactly as-is."
Here's I'd remark that Traversable
is a kind of specialized Functor
, not a "generalization" of it. One of the key facts about any Traversable
(or, actually, about Foldable
, which Traversable
extends) is that it requires that the elements of any structure have a linear order—you can turn any Traversable
into a list of its elements (with Foldable.toList
).
Another, less obvious fact about Traversable
is that the following functions exist (adapted from Gibbons & Oliveira, "The Essence 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)
A Traversable
instance for sets would violate the proposed law, because all non-empty sets would have the same Shape
—the set whose Contents
is [()]
. From this it should be easy to prove that whenever you try to reassemble
a set you would only ever get the empty set or a singleton back.
Lesson? Traversable
"preserves shape" in a very specific, stronger sense than Functor
does.
这篇关于集合,函数和Eq混淆的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!