Haskell 中通用多态 ADT 的函子实例？

Question

在将类别理论应用于泛型编程时，Haskell 做得很好，例如 recursion-schemes 这样的库。但是我不确定的一件事是如何为多态类型创建通用仿函数实例。

如果你有一个多态类型，比如 List 或 Tree，你可以创建一个从 (Hask × Hask) 到 Hask 的函子来表示它们。例如：

data ListF a b = NilF | ConsF a b  -- L(A,B) = 1+A×B
data TreeF a b = EmptyF | NodeF a b b -- T(A,B) = 1+A×B×B

这些类型在 A 上是多态的，但在 B 上是不动点，像这样：

newtype Fix f = Fix { unFix :: f (Fix f) }
type List a = Fix (ListF a)
type Tree a = Fix (TreeF a)

但正如大多数人所知，列表和树也是通常意义上的函子，它们代表 a 中的 "container"，您可以映射一个函数 f :: a -> b获得 b 的容器。

我想弄清楚是否有办法以通用方式使这些类型（固定点）成为 Functor 的实例，但我不确定如何做。到目前为止，我遇到了以下 2 个问题：

1) 首先，必须有一种方法可以在任何多态不动点上定义泛型 gmap。知道 ListF 和 TreeF 等类型是 Bifunctors，到目前为止我已经知道了：

{-# LANGUAGE ScopedTypeVariables #-}
import Data.Bifunctor

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

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

-- To explicitly use inF as the initial algebra
inF :: f (Fix f) -> Fix f
inF = Fix

gmap :: forall a b f. Bifunctor f => (a -> b) -> Fix (f a) -> Fix (f b)
gmap f = cata alg
    where
        alg :: f a (Fix (f b)) -> Fix (f b)
        alg = inF . bimap f id

在 Haskell 中，这给了我以下错误：Could not deduce (Functor (f a)) arising from a use of cata from the context (Bifunctor f)。

我正在使用 bifunctors 包，它有一个 WrappedBifunctor 类型，专门定义了以下实例，可以解决上述问题：Bifunctor p => Functor (WrappedBifunctor p a)。但是，我不确定如何 "lift" 里面的这种类型 Fix 才能使用它

2)即使上面的泛型gmap可以定义，不知道是否可以创建Functor的泛型实例具有 fmap = gmap，并且可以立即用于 List 和 Tree 类型（以及以类似方式定义的任何其他类型）。这可能吗？

如果是这样，是否也可以使其与 recursion-schemes 兼容？

Answer 1

如果你愿意暂时接受你正在处理双函子，你可以说

cata :: Bifunctor f => (f a r -> r) -> Fix (f a) -> r
cata f = f . bimap id (cata f) . unFix

然后

gmap :: forall a b f. Bifunctor f => (a -> b) -> Fix (f a) -> Fix (f b)
gmap f = cata alg
    where
        alg :: f a (Fix (f b)) -> Fix (f b)
        alg = inF . bimap f id

（在 gmap 中，我刚刚重新安排了您的 class 约束以使作用域类型变量起作用。）

您也可以使用 cata 的原始版本，但是您需要 Functor 和 gmap 上的 Bifunctor 约束：

gmap :: forall a b f. (Bifunctor f, Functor (f a)) => (a -> b) -> Fix (f a) -> Fix (f b)
gmap f = cata alg
    where
        alg :: f a (Fix (f b)) -> Fix (f b)
        alg = inF . bimap f id

你不能让你的 gmap 成为普通 Functor class 的实例，因为它需要类似于

instance ... => Functor (\ x -> Fix (f x))

而且我们没有类型级别的 lambda。如果你反转 f 的两个参数，你可以这样做，但是你失去了 "other" Functor 实例并且需要定义 cata 再次针对 Bifunctor。

[您可能也有兴趣阅读 http://www.andres-loeh.de/IndexedFunctors/ 以获得更通用的方法。]

Answer 2

TBH 我不确定这个解决方案对你有多大帮助，因为它仍然需要额外的 newtype 包装这些定点函子，但我们开始吧：

如果你做了一些 wrapping/unwrapping

，你可以继续使用你的通用 cata

给定以下两个辅助函数：

unwrapFixBifunctor :: (Bifunctor f) => Fix (WrappedBifunctor f a) -> Fix (f a)
unwrapFixBifunctor = Fix . unwrapBifunctor . fmap unwrapFixBifunctor . unFix

wrapFixBifunctor :: (Bifunctor f) => Fix (f a) -> Fix (WrappedBifunctor f a)
wrapFixBifunctor = Fix . fmap wrapFixBifunctor . WrapBifunctor . unFix

您可以定义 gmap 而对 f 没有任何附加限制：

gmap :: (Bifunctor f) => (a -> b) -> Fix (f a) -> Fix (f b)
gmap f = unwrapFixBifunctor . cata alg . wrapFixBifunctor
  where
    alg = inF . bimap f id

您可以通过 `newtype`

将 Fix . f 变成 Functor

我们可以通过将此 "type-level lambda" 实现为 newtype:

来实现 \a -> Fix (f a) 的 Functor 实例

newtype FixF f a = FixF{ unFixF :: Fix (f a) }

instance (Bifunctor f) => Functor (FixF f) where
    fmap f = FixF . gmap f . unFixF

Answer 3

bifunctors 软件包还提供了一个特别合适的 Fix 版本：

newtype Fix p a = In {out :: p (Fix p a) a}

这很容易成为 Functor 实例：

instance Bifunctor p => Functor (Fix p) where
  fmap f = In . bimap (fmap f) f . out

Haskell 中通用多态 ADT 的函子实例？

Functor instance for generic polymorphic ADTs in Haskell?

haskell

recursion

functor

category-theory

如果你做了一些 wrapping/unwrapping

您可以通过 `newtype`

Haskell 中通用多态 ADT 的函子实例？

Functor instance for generic polymorphic ADTs in Haskell?

haskell

recursion

functor

category-theory

如果你做了一些 wrapping/unwrapping

您可以通过 newtype

您可以通过 `newtype`