如何使用 Fix 类型的 Functor 实例

Question

假设我想要一个非常通用的 ListF 数据类型：

{-# LANGUAGE GADTs, DataKinds #-}

data ListF :: * -> * -> * where
  Nil  ::           List a b
  Cons :: a -> b -> List a b

现在我可以将此数据类型与 Data.Fix 一起使用来构建 f-代数

import qualified Data.Fix as Fx

instance Functor (ListF a :: * -> *) where
  fmap f (Cons x y) = Cons x (f y)
  fmap _ Nil        = Nil

sumOfNums = Fx.cata f (Fx.Fix $ Cons 2 (Fx.Fix $ Cons 3 (Fx.Fix $ Cons 5 (Fx.Fix Nil))))
  where
    f (Cons x y) = x + y
    f Nil        = 0

但是我如何使用这种非常通用的数据类型 ListF 创建我认为是递归列表的默认 Functor 实例（映射列表中的每个值）

我想我可以使用 Bifunctor（映射第一个值，遍历第二个值），但我不知道它如何与 Data.Fix.Fix 一起工作？

Answer 1

I guess I could use a Bifunctor (mapping over the first value, traversing the second), but I don't know how that could ever work with Data.Fix.Fix?

你一语中的。

The bifunctors package contains a "Fix-for-bifunctors" type 看起来像这样：

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

只要 f 是 Bifunctor，

Fix f 就是 Functor。 fmap 递归地 fmaps f 的第一个参数并映射第二个参数。

instance Bifunctor f => Functor (Fix f) where
    fmap f = In . bimap (fmap f) f . out

因此您的 List 示例将如下所示：

data ListF r a = Nil | Cons r a

type List = Fix ListF

map :: (a -> b) -> List a -> List b
map = fmap

Answer 2

通过采用双函子的不动点构造递归函子是非常正确的，因为 1 + 1 = 2。列表节点结构作为具有 2 种子结构的容器给出："elements" 和 "sublists".

令人不安的是，我们需要 Functor 的另一个完整概念（尽管它的名称相当笼统，它捕获了相当具体的函子种类），以构建一个 Functor 作为固定点.然而，我们可以（作为一个噱头）转移到一个稍微更一般的函子概念，即在不动点下封闭。

type p -:> q = forall i. p i -> q i

class FunctorIx (f :: (i -> *) -> (o -> *)) where
  mapIx :: (p -:> q) -> f p -:> f q

这些是 索引集 上的函子，因此这些名称不仅仅是对 Goscinny 和 Uderzo 的无端致敬。您可以将 o 视为 "sorts of structure"，将 i 视为 "sorts of substructure"。这是一个示例，基于 1 + 1 = 2.

data ListF :: (Either () () -> *) -> (() -> *) where
  Nil  :: ListF p '()
  Cons :: p (Left '()) -> p (Right '()) -> ListF p '()

instance FunctorIx ListF where
  mapIx f Nil        = Nil
  mapIx f (Cons a b) = Cons (f a) (f b)

要利用子结构排序的选择，我们需要一种类型级别的案例分析。我们不能逃避类型函数，因为

我们需要它被部分应用，这是不允许的；
我们需要在运行时间告诉我们存在哪种类型。

data Case :: (i -> *) -> (j -> *) -> (Either i j -> *)  where
  CaseL :: p i -> Case p q (Left i)
  CaseR :: q j -> Case p q (Right j)

caseMap :: (p -:> p') -> (q -:> q') -> Case p q -:> Case p' q'
caseMap f g (CaseL p) = CaseL (f p)
caseMap f g (CaseR q) = CaseR (g q)

现在我们可以取定点了：

data Mu :: ((Either i j -> *) -> (j -> *)) ->
           ((i -> *) -> (j -> *)) where
  In :: f (Case p (Mu f p)) j -> Mu f p j

在每个子结构位置，我们进行 case split 以查看我们是否应该具有 p 元素或 Mu f p 子结构。我们得到了它的函子性。

instance FunctorIx f => FunctorIx (Mu f) where
  mapIx f (In fpr) = In (mapIx (caseMap f (mapIx f)) fpr)

要根据这些内容构建列表，我们需要在 * 和 () -> * 之间进行权衡。

newtype K a i = K {unK :: a}

type List a = Mu ListF (K a) '()
pattern NilP :: List a
pattern NilP       = In Nil
pattern ConsP :: a -> List a -> List a
pattern ConsP a as = In (Cons (CaseL (K a)) (CaseR as))

现在，对于列表，我们得到

map' :: (a -> b) -> List a -> List b
map' f = mapIx (K . f . unK)

如何使用 Fix 类型的 Functor 实例

How to use Functor instances with Fix types

haskell

functor

fixpoint-combinators