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)

但是，笼统地说，列表和树也是一种函子，它们代表了一个“容器”包含了 a 的值，你可以映射函数 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内部以便使用它。

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

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

- gonzaw

---

这是法定提醒，因为“ADT”既代表“代数数据类型”又代表“抽象数据类型”，而这两个概念截然相反，所以术语“ADT”毫无意义，最好避免使用。 - pigworker

@pigworker：我们从现在开始称它们为uGADTs，怎么样？ - leftaroundabout

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

您也可以使用原始版本的 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))

而我们没有类型级别的lambda。如果您颠倒f的两个参数，则可以做到这一点，但是那样您将失去“其他”Functor实例，并且需要重新定义特定于Bifunctor的cata。

[您可能还有兴趣阅读http://www.andres-loeh.de/IndexedFunctors/以获取更一般的方法。]

- kosmikus

---

有没有可能用不同的方式来解决这个问题，使得编写“Functor”的实例成为可能？例如，使用不同的类型、类型类等等？ - gonzaw

Answer 2

说实话，我不确定这个解决方案对你有多大帮助，因为它仍然需要额外的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

你可以在没有额外的限制 f 的情况下定义 gmap：

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

我们可以通过实现这个“类型级别的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

- Cactus

---

bimap f id 应该写成 Data.Bifunctor.first。 - dfeuer

Answer 3

包还提供了一个特别适合的版本：

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

这可以很容易地将其制作为一个Functor实例：

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

- dfeuer