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的“容器”，您可以映射函数f :: a -> b来获得b的容器。

我正在试图找出是否有一种方法可以使这些类型(不动点)以通用方式成为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中，这会给出以下错误：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)。但是，我不知道如何在Fix中“提升”这种类型才能使用它

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

如果是这样的话，是否也有可能使其与recursion-schemes兼容？

Answer 1

我不知道这个解决方案对您有多大帮助，因为对于这些不动点函子，它仍然需要额外的newtype包装，但我们现在开始：

如果您执行一些包装/展开操作，可以继续使用您的通用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

您可以通过一个Fix . f将Functor变成newtype。

通过将此“类型级别lambda”实现为一个Functor，我们可以为\a -> Fix (f a)实现一个newtype实例。

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

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

Answer 2

如果你现在愿意接受，你可以这么说

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中，我刚刚重新安排了类约束，以使作用域类型变量正常工作。)

您也可以使用原始版本的cata，但随后需要gmap上的Functor和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类的实例，因为它需要类似于

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

我们没有类型级别的蓝光。如果您反转了f的两个参数，您就可以做到这一点，但随后丢失了“其他”Functor实例，并且需要再次定义特定于Bifunctor的cata。

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

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