Haskell中泛型多态ADT的函数实例？

Question

当涉及到将类别理论应用于泛型编程时，Haskell做得非常好，例如recursion-schemes这样的库。但是，我不确定的一点是如何为多态类型创建泛型函数实例。

如果您有一个多态类型，比如列表或树，您可以创建一个from（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

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

我试图找出是否有一种方法可以使这些类型（固定点）成为functor的一个通用实例，但我不确定如何实现。到目前为止，我遇到了以下两个问题：

1）首先，必须有一种方法来定义任何多态固定点上的泛型GMAP。知道像listf和treef这样的类型是双函数，到目前为止我已经知道了以下内容：

{-# 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中，这给了我以下错误:不能从上下文（Bifunctor f)中推导（Functor（f a））。

2）即使可以定义上面的泛型GMAP，我也不知道是否可以创建一个泛型fmap=gmap函数实例，该实例具有fmap=gmap，并且可以立即同时处理上面的list和tree类型（以及以类似方式定义的任何其他类型）。这可能吗？

如果是这样的话，是否也可以使其与递归方案兼容？

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约束，以使作用域类型变量能够工作。）

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

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

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