Haskell中Zap Functor和zap函数的用途是什么？

Question

我在Haskell 遇到了这个结构.我找不到任何关于如何在实际代码中使用zap/ zapWith和bizap/的示例或解释bizapWith.它们在某种程度上与标准zip/ zipWith功能相关吗？如何在Haskell代码中使用Zap/ Bizapfunctor？他们有什么好处？

Answer 1

这个精彩的Kmett博客文章,Cofree Comonad和表达问题涵盖了这一点.不幸的是,博客文章中有相当多的术语,我自己并不完全了解所有内容,但我们可以尝试勾勒出细节.

豌豆数字

让我们以一种非常奇怪的方式定义自然数.我们将首先定义Peano零和后继功能:

zero :: ()
zero = ()

incr :: a -> Identity a
incr = Identity

然后我们可以定义一些数字:

one :: Identity ()
one = incr zero

two :: Identity (Identity ())
two = incr . incr $ zero

three :: Identity (Identity (Identity ()))
three = incr . incr . incr $ zero

奇怪,但它似乎工作.你可以转换3 :: Int到three和背部.(尝试一下.)我们可以编写一个函数f来将任意数字转换为我们奇怪的表示并返回吗？很不幸的是,不行.Haskell类型系统不会让我们构造一个无限类型,这是我们想要的类型f.

一个更大的问题是,作为一个懒惰的函数式程序员,我希望停止输入Identity这么多次.按此速率,我将被迫键入O(n ^ 2)次来定义n个数字.这是2016年,我发现这是不可接受的.

我们可以转向Free数据类型以获取有关我们两个问题的帮助.(有些人称之为免费monad,但当我们只能说"打字"时,我们没有理由说"monad".)

newtype Free f a = Free (Either a (f (Free f a)))

zero :: a -> Free Identity a
zero x = Free (Left x)

incr :: Free Identity a -> Free Identity a
incr = Free . Right . Identity

one :: a -> Free Identity a
one x = incr (zero x)

two :: a -> Free Identity a
two x = incr (incr (zero x))

three :: a -> Free Identity a
three = incr . incr . incr . zero

漂亮.这(令人惊讶的可能)与Identity上面我们不寻常的表示相同.

流

现在让我们尝试构建一个流.比如说,从2000年(2000年,2400年,2800年)开始的百年闰年流.但是以一种奇怪的方式.

unfold :: (a -> a) -> a -> (a, (a, (a, ...)))
unfold a2a a = (a, unfold a2a (a2a a))

centurials :: (Int, (Int, (Int, ...)))
centurials = unfold (+ 400) 2000

假设编译器允许我们写下无限类型,这将是数字流的合适表示.为了拯救Cofree,Free的"双重"类型.在类别理论意义上的双重性,如果你花时间并拿出一个类别理论教科书并煮了很多咖啡并绘制了分类图,然后翻转所有箭头,你会从一个到另一个(或者另一个).这种糟糕的解释必须足以作为关于二元性的手势段落.

newtype Cofree f a = Cofree (a, f (Cofree f a))

unfold :: Functor f => (a -> f a) -> a -> Cofree f a
unfold a2fa a = Cofree (a, fmap (unfold a2fa) (a2fa a))

centurials :: Cofree Identity Int
centurials = unfold (Identity . (+ 400)) 2000

这(也许令人惊讶的是)可能相当于上面我们无限的俄罗斯嵌套玩偶.

使用Peano数字索引流

但是如何寻找流中的特定元素？通过利用Free和Cofree之间的二元性,我们实际上可以使用我们的Peano数字表示来索引我们的流表示.

事实证明,在Haskell中,如果f并且g在数学意义上是双重的,则以下属性成立:

class Zap f g | f -> g, g -> f where
  zap :: (a -> b -> r) -> f a -> g b -> r

我们将不得不忽略关于二元性的讨论以及为什么这个属性适用于双重函子.

我们可以实现最简单的实例:身份函子(在Haskell中表示为newtype Identity a = Identity a)与其自身之间的数学对偶性.

instance Zap Identity Identity where
  zap ab2r (Identity a) (Identity b) = ab2r a b

这个属性也可以扩展到bifunctors:

class Bizap f g | f -> g, g -> f where
  bizap :: (a -> c -> r) -> (b -> d -> r) -> f a b -> g c d -> r

我们可以为Haskell的sum和product编码实例化这个类,它们在类别理论中是(非平凡的!)双重的:

instance Bizap Either (,) where
  bizap ac2r bd2r (Left a) (c, d) = ac2r a c
  bizap ac2r bd2r (Right b) (c, d) = bd2r b d

instance Bizap (,) Either where
  bizap ac2r bd2r (a, b) (Left c) = ac2r a c
  bizap ac2r bd2r (a, b) (Right d) = bd2r b d

我们现在有足够的机器在Free和Cofree之间的Haskell中显示相同的二元性.

instance Zap f g => Zap (Cofree f) (Free g) where
  zap ab2r (Cofree as) (Free bs) = bizap ab2r (zap (zap ab2r)) as bs

instance Zap f g => Zap (Free f) (Cofree g) where
  zap ab2r (Free as) (Cofree bs) = bizap ab2r (zap (zap ab2r)) as bs

这些实例利用要么和双重bifunctor性质(,)以及继承zap从对偶f和g,这在我们的例子中总是会Identity与Identity以"unpeel"的层离Free和Cofree,并递归地调用zap在该下层.

最后,让我们看看它的实际效果:

year2800 :: Int
year2800 = zap id (two id) centurials

通过利用这个zap或"annhilation"属性,我们能够使用由Free构建的自然数索引从Cofree构建的流中检索值.虽然远非现实世界的例子,但代码存在于我们如何在Haskell类型和类型类中对类别理论中的高falutin思想进行编码的练习中.我们能够做到这一点是一个脑筋急转弯,也是我们选择Free和Cofree类型的理智检查.

您可能会发现这些实例对单行有用,或者您的数据结构恰好排列正确,如Gurkenglas的回答中所详述.如果您发现二元性是一个有用的属性可以利用,那么绝对可以达到类别附加包的这一部分.但即使我们找不到它的用法,我们当然可以欣赏整齐地融合在一起的美丽.

至于拉链

你认为Zap和Zip之间存在联系是正确的.它们以Kmett的文字游戏开发风格命名.编码zippable函子导致一个非常相似的类型类Zip:

class Functor f => Zip f where
  fzipWith :: (a -> b -> c) -> f a -> f b -> f c

您可以通过遵循此构造为树和流(再次使用Cofree)派生通用压缩函数.有关详细信息,请参阅博客文章.

Answer 2

Zap涉及双重函数.在Haskell中,这意味着一个人携带额外的信息而另一个人使用它,而这一切都是他们所做的.(r, a) 是一个带有额外r值的值,r -> b是首先需要r值的ab值.zapWith (+) read ("123", 321)将"123"插入读取,并将123和321插入(+).Zap如果您找到适合的代码,那么所有这些都有助于插入.zap = uncurry对于这个例子,顺便说一下.Reader并且Coreader是同构((->) r)和((,) r)分别.其他实例将是一个提供两个值,另一个使用up,或者f提供r,然后使用s,而g提供s,然后用完r.