haskell 什么是反变函子?

wyyhbhjk  于 2022-11-14  发布在  其他
关注(0)|答案(5)|浏览(175)

那类型让我大吃一惊:

class Contravariant (f :: * -> *) where
  contramap :: (a -> b) -> f b -> f a

然后我读了this,但与标题相反,我并没有得到更多的启发。
有人能给予一下什么是反变函子吗?

4urapxun

4urapxun1#

从程序员的Angular 来看,函子性的本质是能够轻松地“适应”事物。我这里所说的“适应”是指,如果我有一个f a,而我需要一个f b,我希望有一个适配器,它能把我的f a装进我的f b形状的洞里。
如果我能把一个a转换成一个b,那么我就能把一个f a转换成一个f b,这就是Haskell的Functor类所体现的模式;如果我提供一个a -> b函数,那么fmap允许我将f a的内容修改为f b的内容,而不用担心f所涉及的任何内容。1
当然,这里讨论的是参数化类型,如list-of-x [x]Maybe yIO z,我们可以使用适配器更改的是xy,或者z。如果我们想要从任何可能的函数a -> b中获得适配器的灵活性,那么当然我们需要环适配必须同样适用于任何可能的类型。
不那么直观的是(一开始),有些类型可以用几乎与函式类型完全相同的方式进行适应,只是它们是“向后的”;对于这些,如果我们想修改一个f a来满足对f b的需求,我们实际上需要提供一个b -> a函数,而不是a -> b函数!
我最喜欢的具体例子实际上是a -> r类型的函数(a代表参数,r代表结果);所有这些抽象的废话在应用于函数时都非常有意义(如果您做过任何实质性的编程,您几乎肯定在不了解术语或它们的广泛适用性的情况下使用过这些概念),并且在这种情况下,这两个概念显然是相互对立的。
众所周知,a -> rr中的一个函子。如果我有一个a -> r,而我需要一个a -> s,那么我可以使用一个r -> s函数,通过对结果进行后处理来修改我的原始函数。2
另一方面,如果我有一个a -> r函数,而我需要的是一个b -> r,那么很明显,我可以通过在将参数传递给原始函数之前对它们进行预处理来满足我的需要。不管我做什么,它总是期望a输入。所以我需要把我的b值转换成它期望的a值:我的预处理适配器需要一个b -> a函数。
我们刚才看到的是a -> r类型的函数在r中是一个 * 协变 * 函子,在a中是一个 * 逆变 * 函子。我认为这就是说我们可以修改函数的结果,结果类型随着适配器r -> s“变化”。而当我们适配函数的参数时,参数类型会向适配器的“相反方向”改变。
有趣的是,函数结果fmap和函数参数contramap的实现几乎完全相同:只是函数组合(.运算符)!唯一的区别是在哪一端组合适配器函数:3

fmap :: (r -> s) -> (a -> r) -> (a -> s)
fmap adaptor f = adaptor . f
fmap adaptor = (adaptor .)
fmap = (.)

contramap' :: (b -> a) -> (a -> r) -> (b -> r)
contramap' adaptor f = f . adaptor
contramap' adaptor = (. adaptor)
contramap' = flip (.)

我认为每个区块的第二个定义是最有见地的;(协变地)Map到函数的结果是左边的复合(如果我们想采取“this-happens-after-that”的观点,则是后复合),而反变地Map到函数的参数是右边的复合(前复合)。
这种直觉很好地概括了;如果f x结构可以 * 给予我们 * x类型的值(就像a -> r函数至少潜在地给我们r值一样),它可能是x中的协变Functor,我们可以使用x -> y函数将其修改为f y。但如果f x结构从我们这里接收x类型的值(同样,就像a -> r函数的参数是a类型),那么它可能是Contravariant函子,我们需要使用y -> x函数将其修改为f y
我发现有趣的是,“来源是协变的,当你从源/目标的 * 实现者 * 而不是调用者的Angular 思考时,“目标是逆变的”直觉就会颠倒过来。(同时仍然向调用者提供“接收x值”接口)。即使作为f x的实现者,我也会考虑调整我调用的内容,而不是“调整我的调用者接口”。

我对Contravariant唯一的半真实世界的使用(与通过使用右边的组合在参数中隐式使用函数的逆变相反,这是非常常见的)是用于可以序列化x值的Serialiser a类型。Serialiser必须是Contravariant而不是Functor;如果我可以序列化Foos,我也可以序列化Bars,如果我可以Bar -> Foo。4但是当你意识到Serialiser a基本上是a -> ByteString时,这就变得很明显了;我只是在重复a -> r示例中的一个特例。
在纯函数式编程中,“接收值”但不返回值的函数没有多大用处,因此所有的逆变函子看起来都像函数,但几乎任何可以包含任意类型值的简单数据结构都将是该类型参数中的协变函子。(Functor被认为是Monad的基本组成部分,在Functor在Haskell中被定义为一个类之前,Monad就已经被广泛使用了)。
在命令式OO中,我相信逆变函子可能更为常见(但没有像Contravariant这样的统一框架进行抽象),尽管它也很容易具有可变性,并且副作用意味着参数化类型根本不可能是函子(通常是:你的a的标准容器既可读又可写,它既是a的发射器又是接收器,而不是意味着它既是协变的又是逆变的,事实证明它既不是也不是)。
1每个fFunctor示例说明如何将任意函数应用于该f的特定形式,而不用担心f所应用的特定类型;很好地分离了关注点。
2这个函子也是一个单子,等价于Reader单子。在这里我不打算详细讨论函子,但考虑到我的帖子的其余部分,一个明显的问题是“那么a -> r类型也是a中的某种逆变单子吗?"不幸的是,逆变不适用于单子(参见Are there contravariant monads?),但是存在Applicative的逆变类似物:https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant-Divisible.html
3请注意,这里的contramap'与Haskell中实现的Contravariant中的实际contramap不匹配;在Haskell代码中,不能仅仅因为a不是(->)的最后一个类型参数,就将a -> r作为Contravariant的实际示例。* 从概念上讲,* 它工作得非常好,而且您总是可以使用一个newtype Package 器来交换类型参数,并将其作为示例(逆变定义Op类型就是为了实现此目的)。
4至少对于“序列化”的定义,它不一定包括能够在以后重建Bar,因为它将序列化与它Map到的Foo相同的Bar,而没有办法包括关于Map是什么的任何信息。

tquggr8v

tquggr8v2#

首先,@haoformayor的回答很好,所以这更多的是一个补充,而不是一个完整的回答。

定义

我喜欢从图的Angular 来思考函子(协变/逆变)。其定义反映在下面的图中。(我将contramap缩写为cmap

covariant                           contravariant
f a ─── fmap φ ───▶ f b             g a ◀─── cmap φ ─── g b
 ▲                   ▲               ▲                   ▲
 │                   │               │                   │
 │                   │               │                   │
 a ────── φ ───────▶ b               a ─────── φ ──────▶ b

注意:这两个定义的唯一变化是顶部的箭头,(嗯和名称,所以我可以把它们称为不同的东西)。

示例

在谈到这些时,我总是想到函数的例子--然后f的一个例子是type F a = forall r. r -> a(这意味着第一个参数是任意的,但r是固定的),或者换句话说,所有的函数都有一个公共输入,(协变)Functor的例子就是fmap ψ φ = ψ . φ '。
其中(逆变)Functor是所有具有公共结果-type G a = forall r. a -> r的函数,这里Contravariant示例将是cmap ψ φ = φ . ψ
但这到底是什么意思
φ :: a -> bψ :: b -> c

  • 通常 * 因此(ψ . φ) x = ψ (φ x)x ↦ y = φ xy ↦ ψ y是有意义的,在cmap的语句中省略的是这里

φ :: a -> bψ :: **c -> a**
因此ψ不能接受φ的结果,但它可以将其参数转换为φ可以使用的内容-因此x ↦ y = ψ xy ↦ φ y是唯一正确的选择。
这在下面的图表中得到了反映,但在这里,我们已经将具有公共源/目标的函数的例子抽象为具有协变/逆变性质的东西,这是你在数学和/或 haskell 中经常看到的东西。

covariant
f a ─── fmap φ ───▶ f b ─── fmap ψ ───▶ f c
 ▲                   ▲                   ▲
 │                   │                   │
 │                   │                   │
 a ─────── φ ──────▶ b ─────── ψ ──────▶ c

               contravariant
g a ◀─── cmap φ ─── g b ◀─── cmap ψ ─── g c
 ▲                   ▲                   ▲
 │                   │                   │
 │                   │                   │
 a ─────── φ ──────▶ b ─────── ψ ──────▶ c

备注:

在数学中,你通常需要一个定律来称某个东西为函子。

covariant
   a                        f a
  │  ╲                     │    ╲
φ │   ╲ ψ.φ   ══▷   fmap φ │     ╲ fmap (ψ.φ)
  ▼    ◀                   ▼      ◀  
  b ──▶ c                f b ────▶ f c
    ψ                       fmap ψ

       contravariant
   a                        f a
  │  ╲                     ▲    ▶
φ │   ╲ ψ.φ   ══▷   cmap φ │     ╲ cmap (ψ.φ)
  ▼    ◀                   │      ╲  
  b ──▶ c                f b ◀─── f c
    ψ                       cmap ψ

这就相当于说

fmap ψ . fmap φ = fmap (ψ.φ)

反之

cmap φ . cmap ψ = cmap (ψ.φ)
bq8i3lrv

bq8i3lrv3#

首先,请注意我们的朋友Functor类

你可以把Functor f想象成一个Assert,即a永远不会出现在“否定位置”上。请注意,在以下数据类型中,a似乎充当“result”变量。

  • newtype IO a = IO (World -> (World, a))
  • newtype Identity a = Identity a
  • newtype List a = List (forall r. r -> (a -> List a -> r) -> r)

在以上每个例子中,a都出现在正的位置。在某种意义上,每种类型的a都代表一个函数的“结果”。把第二个例子中的a看作() -> a可能会有所帮助。记住第三个例子等价于data List a = Nil | Cons a (List a)可能会有所帮助。在像a -> List -> r这样的回调中,a出现在负的位置,但是 * 回调本身 * 在负的位置,所以负和负相乘为正。
此方案用于对函数的参数进行签名,其方案为elaborated in this wonderful blog post
现在请注意,这些类型中的每一个都允许一个Functor。这是没有错误的!函子是用来模拟范畴协变函子的思想的,它“保持箭头的顺序”,即f a -> f bf b -> f a相对。在Haskell中,a从不出现在负位置的类型总是允许Functor。我们说这些类型在a上协变。
换句话说,我们可以将Functor类重命名为Covariant,它们是同一个概念。
这个概念之所以用“never”这个词表达得如此奇怪,是因为a既可以出现在正位置也可以出现在负位置,在这种情况下,我们说该类型在a上是不变的。a也可以永远不出现(比如一个幻像类型),在这种情况下,我们说该类型在a上既是协变的也是逆变的--双变的。

回到逆变

因此对于a从不出现在正数位置的类型,我们说该类型在a中是逆变的。每个这样的类型Foo a都允许一个instance Contravariant Foo。下面是一些例子,取自contravariant包:

  • data Void aa为体模)
  • data Unit a = Unita再次为体模)
  • x1米34英寸
  • x1米35英寸
  • x1米36英寸1x
  • x1米37英寸1x

在这些例子中,a要么是双变的,要么仅仅是逆变的。a要么从不出现,要么是负的(在这些人为的例子中,a总是出现在箭头之前,所以确定这是非常简单的)。
更直观的做法是先观察这些类型(表现出逆变性),然后再观察上面的类型(表现出协变性),看看你是否能直观地发现a语义上的差异,也许这是有帮助的,也许这只是一种深奥的花招。
例如,我们想按芯片的种类来划分一个cookie列表,我们有一个chipEquality :: Chip -> Chip -> Bool,要得到一个Cookie -> Cookie -> Bool,我们只需计算runEquivalence . contramap cookie2chip . Equivalence $ chipEquality
相当冗长!但是解决新类型导致的冗长问题将是另一个问题...

其他资源(找到后在此处添加链接)

wr98u20j

wr98u20j4#

我知道这个答案不会像其他答案那样学术性很强,但它只是基于你会遇到的逆变的常见实现。
首先,提示:不要像阅读好的ol' Functor的map那样,使用对f的心理隐喻来阅读contraMap函数类型。
你知道你是怎么想的:
“包含(或产生)t的事物“
......当您读取f t之类的类型时?
好吧,在这种情况下,你需要停止这样做。
反变函子是经典函子的“对偶”,所以,当你在contraMap中看到f a时,你应该想到“对偶”隐喻:
f t是一个 * 消耗 * 一个t的东西
现在contraMap的类型应该开始有意义了:
contraMap :: (a -> b) -> f b ...
......就在这里停顿一下,而这种类型是完全合理的:
1.一个“产生”b的函数。
1.一个“消耗”一个b的东西。
第一个参数煮b。第二个参数吃b
有道理,对吧?
现在完成编写类型:
contraMap :: (a -> b) -> f b -> f a
所以最后这个东西必须产生一个“a的 * 消费者 *“。
当然我们可以构建它,假设我们的第一个参数是一个函数,它的输入是a.
函数(a -> b)应该是构建“a的消费者“的一个很好的构建块。
所以contraMap基本上可以让你创建一个新的“消费者”,就像这样(警告:组成符号输入):
(takes a as input / produces b as output) ~~> (consumer of b)

  • 在我编的符号左边:contraMap的第一个参数(即(a -> b))。
  • 右边:第二个参数(即f b)。
  • 整个事情粘在一起:contraMap的最终输出(知道如何使用a的东西,即f a)。
evrscar2

evrscar25#

关于这个主题的另一种观点,局限于被视为逆变函子的 * 函数 *。(另见this。)

* 函数 * 作为其结果的 * 容器 (因此 * Functor s

一个a -> b类型的函数f可以被认为包含一个b类型的值,当我们给f输入一个a类型的值时,我们就可以访问这个值。
现在,作为其他事物的容器的事物可以成为Functor s,在某种意义上,我们可以通过将fmap g应用于函子本身,将函数g应用于它们的内容。
因此,a -> b类型的f可以看作是b中的函子,即(->) a可以成为Functor。为此,我们需要定义fmapfmapf的“内容”上ping函数g本质上意味着将g应用于f返回的任何内容(显然,一旦它被提供了a类型的输入),这意味着fmap g f = \x -> g (f x),或者更简单地说,fmap g f = g . f

* 对a -> b函数执行fmap ping * = * 后处理 * 它们的b类型的结果

作为最后一个想法:a -> b类型的函数是b中的函子,因为我们可以通过函数b -> c(其中c只是另一个类型)***后***处理它。

* 对a -> b函数执行contramap ping * = * 预处理 * 一个输入以获取a

但是,如果我们想使用一个函数g(类型为c -> a)来***预***处理一个c类型的值,以获得a类型的值,并将其传递给f,该怎么办?
很明显,在这种情况下,我们希望gf之前行动,也就是说,我们要寻找f . g
我们希望f . g是“将gMap到f“这一概念的“实现”,换句话说,我们需要whichmap g f = f . g
你猜怎么着?whichmap实际上是contramap的函数实现!而contramap是你必须实现的,以使某个类型成为Contravariant函子类型类的示例。
嗯,不是真的......
实际上并不存在Contravariantinstance镜像instance Functor ((->) r),我相信这仅仅是因为instance Contravariant (-> r)/instance Contravariant (flip (->) r)是无效的语法;因此创建了另一个类型,

newtype Op a b = Op { getOp :: b -> a }

且***此***被作为Contravariant示例:

instance Contravariant (Op a) where
  contramap f g = Op (getOp g . f)

最后两段代码取自hackage。
this页面顶部的例子也很有启发性。

相关问题