在将范畴论应用于通用编程方面,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
兼容?