Haskell中泛型多态ADT的Functor实例？

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)

但是大多数人都知道,列表和树也是通常意义上的仿函数,它们代表了as 的"容器" ,你可以映射一个函数f :: a -> b来获取容器b.

我试图找出是否有办法以Functor通用的方式使这些类型(固定点)成为一个实例,但我不确定如何.到目前为止我遇到了以下两个问题:

---

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).但是,我不知道如何"提升"这种类型的内部Fix能够使用它

2)即使通用gmap上面可以定义,我不知道是否有可能创建一个通用的例子Functor有fmap = gmap,可同时为即时工作List和Tree类型那里(以及类似的定义的任何其他类型的时尚).这可能吗？

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

Answer 1

你可以说,如果你愿意接受你正在与bifunctors打交道的那一刻

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,但是您需要 Functor以下Bifunctor约束和约束gmap:

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))

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

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

Answer 2

TBH我不确定这个解决方案对你有多大帮助,因为它仍然需要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