haskell - 什么是双仿函数？

Question

我对 Haskell 比较陌生，无法理解双仿函数的实用性。我想我在理论上理解它们:例如，如果我想映射一个抽象多个具体类型的类型，例如 Either 或 Maybe，我需要将它们封装在双仿函数中。但一方面，这些示例似乎特别做作，另一方面，您似乎可以简单地通过组合来实现相同的功能。

举个例子，我在 The Essence of the Iterator Pattern 中遇到了这段代码作者:杰里米·吉本斯 (Jeremy Gibbons) 和布鲁诺·C. d. S.奥利维拉:

import Data.Bifunctor

data Fix s a = In {out::s a (Fix s a) }

map' :: Bifunctor s => (a -> b) -> Fix s a -> Fix s b
map' f = In . bimap f (map' f) . out

fold' :: Bifunctor s => (s a b -> b) -> Fix s a -> b
fold' f = f . bimap id (fold' f) . out

unfold' :: Bifunctor s => (b -> s a b) -> b -> Fix s a
unfold' f = In . bimap id (unfold' f) . f

我理解重点是组合映射和折叠函数来创建迭代器模式，这是通过定义需要两个参数的数据构造函数来实现的。但实际上我不明白这与使用常规仿函数并使用 fmap 而不是 bimap 组合函数有什么不同。我想我显然一定遗漏了一些东西，无论是在这个例子中，还是在一般情况下。

Answer 1

我觉得你有点想太多了。双仿函数就像一个二参数仿函数。 Gibbons 和 Oliveira 的想法只是双仿函数的一种应用，就像递归方案的标准动物园只是仿函数的一种应用一样。

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d

Bifunctor 具有一种 * -> * -> * 并且两个参数都可以协变映射。将此与常规仿函数进行比较，后者只有一个可以协变映射的参数 (f::* -> *)。

例如，考虑一下 Either 的常用 Functor 实例。它只允许您对第二个类型参数进行fmap - Right 值得到映射，Left 值保持原样。

instance Functor (Either a) where
    fmap f (Left x) = Left x
    fmap f (Right y) = Right (f y)

但是，它的 Bifunctor 实例允许您映射总和的两半。

instance Bifunctor Either where
    bimap f g (Left x) = Left (f x)
    bimap f g (Right y) = Right (g y)

对于元组同样如此:(,) 的 Functor 实例允许您仅映射第二个组件，但 Bifunctor 允许您映射两部分。

instance Functor ((,) a) where
    fmap f (x, y) = (x, f y)

instance Bifunctor (,) where
    bimap f g (x, y) = (f x, g y)

请注意，您提到的也许不适合双函数框架，因为它只有一个参数。

<小时/>

关于Fix问题，双仿函数的不动点允许您表征具有仿函数类型参数的递归类型，例如大多数类似容器的结构。让我们以列表为例。

newtype Fix f = Fix { unFix :: f (Fix f) }

data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)

使用标准仿函数 Fix，正如我上面所说，List 的 Functor 实例没有通用派生，因为 Fix 对 List 的 a 参数一无所知。也就是说，我无法编写类似于 instance Something f => Functor (Fix f) 的内容，因为 Fix 的类型错误。我必须手动启动列表的map，也许使用cata:

map :: (a -> b) -> List a -> List b
map f = cata phi
    where phi Nil_ = Fix Nil_
          phi Cons_ x r = Fix $ Cons_ (f x) r

Fix 的双函数版本确实允许 Functor 的实例。 Fix 使用 bifunctor 的参数之一插入 Fix f a 的递归出现，另一个参数代表结果数据类型的 functorial 参数。

newtype Fix f a = Fix { unFix :: f a (Fix f a) }

instance Bifunctor f => Functor (Fix f) where
    fmap f = Fix . bimap f (fmap f) . unFix

所以我们可以写:

deriveBifunctor ''ListF

type List = Fix ListF

并免费获取Functor实例:

map :: (a -> b) -> List a -> List b
map = fmap

当然，如果你想通用地处理具有多个参数的递归结构，那么你需要推广到三仿函数、四仿函数等......这显然是不可持续的，并且需要做大量的工作(在更先进的编程语言)已被投入设计更灵活的系统来表征类型。