haskell - 如何将 Functor 实例赋予为一般递归方案构建的数据类型？

Question

我有一个具有 Functor 实例的递归数据类型:

data Expr1 a
  = Val1 a
  | Add1 (Expr1 a) (Expr1 a)
  deriving (Eq, Show, Functor)

现在，我有兴趣修改此数据类型以支持通用递归方案，如 this tutorial 中所述。和 this Hackage package .我设法让变态起作用:

newtype Fix f = Fix {unFix :: f (Fix f)}

data ExprF a r
  = Val a
  | Add r r
  deriving (Eq, Show, Functor)

type Expr2 a = Fix (ExprF a)

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

eval :: Expr2 Int -> Int
eval = cata $ \case
  Val n -> n
  Add x y -> x + y

main :: IO ()
main =
  print $ eval
    (Fix (Add (Fix (Val 1)) (Fix (Val 2))))

但是现在我不知道如何给 Expr2与原始 Expr 相同的仿函数实例有。尝试定义仿函数实例时似乎存在一种不匹配:

instance Functor (Fix (ExprF a)) where
    fmap = undefined

Kind mis-match
    The first argument of `Functor' should have kind `* -> *',
    but `Fix (ExprF a)' has kind `*'
    In the instance declaration for `Functor (Fix (ExprF a))'

如何为 Expr2 编写 Functor 实例?

我想过用 newtype Expr2 a = Expr2 (Fix (ExprF a)) 将 Expr2 包装在一个新类型中。但是这个新类型需要解包才能传递给 cata ，我不太喜欢。我也不知道是否可以自动推导出 Expr2仿函数实例，就像我对 Expr1 所做的那样.

Answer 1

这对我来说是一个老痛处。关键是你的ExprF它的两个参数都是函数式的。所以如果我们有

class Bifunctor b where
  bimap :: (x1 -> y1) -> (x2 -> y2) -> b x1 x2 -> b y1 y2

然后你可以定义(或想象一台机器为你定义)

instance Bifunctor ExprF where
  bimap k1 k2 (Val a)    = Val (k1 a)
  bimap k1 k2 (Add x y)  = Add (k2 x) (k2 y)

现在你可以拥有

newtype Fix2 b a = MkFix2 (b a (Fix2 b a))

伴随着

map1cata2 :: Bifunctor b => (a -> a') -> (b a' t -> t) -> Fix2 b a -> t
map1cata2 e f (MkFix2 bar) = f (bimap e (map1cata2 e f) bar)

这反过来又让您知道，当您在其中一个参数中取定点时，剩下的仍然是另一个参数

instance Bifunctor b => Functor (Fix2 b) where
  fmap k = map1cata2 k MkFix2

你会得到你想要的。但是你的 Bifunctor实例不会被魔法构建。你需要一个不同的定点运算符和一种全新的仿函数，这有点烦人。问题是你现在有两种子结构:“值”和“子表达式”。

轮到了。 有一个仿函数的概念，它在固定点下是封闭的。打开厨房水槽(尤其是 DataKinds)并

type s :-> t = forall x. s x -> t x

class FunctorIx (f :: (i -> *) -> (o -> *)) where
  mapIx :: (s :-> t) -> f s :-> f t

请注意，“元素”的索引类型超过 i。和“结构”在某种其他 o上的索引.我们采取 i -将元素上的功能保留到 o保留结构上的功能。至关重要的是， i和 o可以不同。

神奇的词是“1、2、4、8，求幂的时间!”。一种类型 *可以很容易地变成一种简单索引的 GADT () -> * .并且可以将两种类型卷在一起制成一种 GADT Either () () -> * .这意味着我们可以将两种子结构组合在一起。一般来说，我们有一种类型级别 either .

data Case :: (a -> *) -> (b -> *) -> Either a b -> * where
  CL :: f a -> Case f g (Left a)
  CR :: g b -> Case f g (Right b)

配备了“ map ”的概念

mapCase :: (f :-> f') -> (g :-> g') -> Case f g :-> Case f' g'
mapCase ff gg (CL fx) = CL (ff fx)
mapCase ff gg (CR gx) = CR (gg gx)

所以我们可以将我们的双因子重构为 Either -索引 FunctorIx实例。

现在我们可以获取任何节点结构的固定点 f其中有两个元素的位置 p或子节点。这和我们上面的交易一样。

newtype FixIx (f :: (Either i o -> *) -> (o -> *))
              (p :: i -> *)
              (b :: o)
  = MkFixIx (f (Case p (FixIx f p)) b)

mapCata :: forall f p q t. FunctorIx f =>
  (p :-> q) -> (f (Case q t) :-> t) -> FixIx f p :-> t
mapCata e f (MkFixIx node) = f (mapIx (mapCase e (mapCata e f)) node)

但是现在，我们得到了 FunctorIx 的事实。在 FixIx 下关闭.

instance FunctorIx f => FunctorIx (FixIx f) where
  mapIx f = mapCata f MkFixIx

索引集上的仿函数(具有改变索引的额外自由)可以非常精确且非常强大。与 Functor 相比，它们享有更多方便的封闭特性。是的。我不认为他们会 catch 。