Haskell中泛型多态ADT的Functor实例？ [英] Functor instance for generic polymorphic ADTs in Haskell?

问题描述

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

如果您有一个多态类型，如List或Tree，你可以从（Hask×Hask）向Hask创建一个代表它们的函子。例如：

 数据ListF a b = NilF | ConsF a b  -  L（A，B）= 1 + A×B 
 data TreeF a b = EmptyF | NodeF abb -T（A，B）= 1 + A×B×B 
  

这些类型是在A上是多态的，但对于B是固定点，如下所示：

  newtype修复f =修正{unFix :: f（Fix f）} 
类型List a = Fix（ListF a）
类型树a =修正（TreeF a）
  

但是，正如大多数人所知道的，列表和树通常也是函子，它们代表 a 的容器，它你可以映射一个函数 f :: a - > b 获取一个 b 的容器。

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

---

1）首先，是一种在任何多态固定点上定义通用 gmap 的方法。知道类型如 ListF 和 TreeF 是Bifunctors，到目前为止我已经得到了这个：

  { - ＃LANGUAGE ScopedTypeVariables＃ - } 
导入Data.Bifunctor 
 
 newtype修复f =修复{unFix :: f（Fix f）} 
 
 cata :: Functor f => （f a  - > a） - >修复f  - > 
 cata f = f。 fmap（cata f）。 unFix 
 
  - 明确使用inF作为初始代数
 inF :: f（Fix f） - >修复f 
 inF =修正
 
 gmap :: forall a b f。双模函数f => （a  - > b） - >修复（f a） - > Fix（f b）
 gmap f = cata alg 
其中
 alg :: f a（Fix（f b）） - >修正（f b）
 alg = inF。 bimap f id 
  

在Haskell中，这给我以下错误：无法推断（Functor（fa））由于使用上下文中的cata（Bifunctor f）而产生。

我使用 bifunctors 包，它有一个 WrappedBifunctor 类型，它专门定义了可解决上述问题的以下实例： Bifunctor p => Functor（WrappedBifunctor p a）。但是，我不知道如何在 Fix 内部解除这种类型以便能够使用它。

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

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

解决方案

TBH我不确定这个解决方案对您有多大帮助，因为它仍然需要额外的 newtype 包装这些定点函子，但是在这里我们继续：

您可以继续使用您的通用 cata code>如果你做一些包装/解包

给定以下两个帮助函数：

  unwrapFixBifunctor ::（Bifunctor f）=> Fix（WrappedBifunctor f a） - >修复（f a）
 unwrapFixBifunctor =修复。 unwrapBifunctor。 fmap unwrapFixBifunctor。 unFix 
 
 wrapFixBifunctor ::（Bifunctor f）=>修复（f a） - >修复（WrappedBifunctor f a）
 wrapFixBifunctor =修复。 fmap wrapFixBifunctor。 WrapBifunctor。 unFix 
  

您可以定义 gmap 在 f ：

  gmap ::（Bifunctor f）=> ; （a  - > b） - >修复（f a） - >修复（f b）
 gmap f = unwrapFixBifunctor。 cata alg。 wrapFixBifunctor 
其中
 alg = inF。 bimap f id 
  

您可以使修正。通过 newtype


$ b将f 转换为 Functor $ b

我们可以为 \ a - >实现一个 Functor 实例。通过实现这个type-level lambda作为 newtype 来修正（fa）：

  newtype FixF fa = FixF {unFixF :: Fix（fa）} 
 
 instance（Bifunctor f）=> Functor（FixF f）其中
 fmap f = FixF。 gmap f。 unFixF 
  

When it comes to applying category theory for generic programming Haskell does a very good job, for instance with libraries like recursion-schemes. However one thing I'm not sure of is how to create a generic functor instance for polymorphic types.

If you have a polymorphic type, like a List or a Tree, you can create a functor from (Hask × Hask) to Hask that represents them. For example:

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

These types are polymorphic on A but are fixed points regarding B, something like this:

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

But as most know, lists and trees are also functors in the usual sense, where they represent a "container" of a's, which you can map a function f :: a -> b to get a container of b's.

I'm trying to figure out if there's a way to make these types (the fixed points) an instance of Functor in a generic way, but I'm not sure how. I've encountered the following 2 problems so far:

---

1) First, there has to be a way to define a generic gmap over any polymorphic fixed point. Knowing that types such as ListF and TreeF are Bifunctors, so far I've got this:

{-# 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

In Haskell this gives me the following error: Could not deduce (Functor (f a)) arising from a use of cata from the context (Bifunctor f).

I'm using the bifunctors package, which has a WrappedBifunctor type that specifically defines the following instance which could solve the above problem: Bifunctor p => Functor (WrappedBifunctor p a). However, I'm not sure how to "lift" this type inside Fix to be able to use it

2) Even if the generic gmap above can be defined, I don't know if it's possible to create a generic instance of Functor that has fmap = gmap, and can instantly work for both the List and Tree types up there (as well as any other type defined in a similar fashion). Is this possible?

If so, would it be possible to make this compatible with recursion-schemes too?

解决方案

TBH I'm not sure how helpful this solution is to you because it still requires an extra newtype wrapping for these fixed-point functors, but here we go:

You can keep using your generic cata if you do some wrapping/unwrapping

Given the following two helper functions:

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

you can define gmap without any additional constraint on f:

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

You can make Fix . f into a Functor via a newtype

We can implement a Functor instance for \a -> Fix (f a) by implementing this "type-level lambda" as a newtype:

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

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

这篇关于Haskell中泛型多态ADT的Functor实例？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！