如何使用具有Fix类型的Functor实例

Question

{-# LANGUAGE GADTs, DataKinds #-}

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

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

Answer 1

用双截断子的不动点构造递归函子是正确的，因为1+1=2。列表节点结构是一个容器，包含两种子结构：“元素”和“子列表”。

麻烦的是，我们需要另一个函子的概念（它捕获了一个相当特定的函子种类，尽管它的名称相当通用）来构造一个函子作为一个不动点。然而，我们可以（作为一点特技）转移到一个稍微更一般的函子概念，它在不动点下是闭合的。

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视为“结构的种类”，将i视为“子结构的种类”。这里有一个例子，基于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)

null

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

在每个子结构位置，我们进行大小写拆分，以查看是否应该有p-element或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)