haskell - 使用变形来忘记 Cofree 注释

Question

我有一个 AST，我正在使用 Cofree 进行注释:

data ExprF a
  = Const Int
  | Add a
        a
  | Mul a
        a
  deriving (Show, Eq, Functor)

我使用 type Expr = Fix ExprF 来表示未标记的 AST，并使用 type AnnExpr a = Cofree ExprF a 来表示标记的。我想出了一个函数，可以通过丢弃所有注释将标记的 AST 转换为未标记的 AST:

forget :: Functor f => Cofree f a -> Fix f
forget = Fix . fmap uncofree . unwrap

这看起来可能是某种变形(我使用的是 Kmett 的 recursion-schemes 包中的定义)。

cata :: (Base t a -> a) -> t -> a
cata f = c where c = f . fmap c . project

我认为使用变质重写的上面看起来像这样，但我无法弄清楚要为 alg 放置什么以使其进行类型检查。

forget :: Functor f => Cofree f a -> Fix f
forget = cata alg where
  alg = ???

任何帮助确定这是否真的是变形/变形的帮助，以及为什么它是/不是的一些直觉将不胜感激。

Answer 1

forget :: Functor f => Cofree f a -> Fix f
forget = cata (\(_ :< z) -> Fix z)
-- (Control.Comonad.Trans.Cofree.:<)
-- not to be confused with
-- (Control.Comonad.Cofree.:<)

说明

只看类型，我们可以证明实际上只有一种方法可以实现 forget .让我们从 cata 的类型开始:

cata :: Recursive t => (Base t b -> b) -> t -> b

在这里t ~ Cofree f a和 type instance of Base for Cofree 给出:

type instance Base (Cofree f a) = CofreeF f a

在哪里 CofreeF 是:

data CoFreeF f a b = a :< f b
-- N.B.: CoFree also defines a (:<) constructor so you have to be
-- careful with imports.

即花哨的配对类型。让我们用实际的对类型替换它以使事情更清楚:

cata :: Functor f => ((a, f b) -> b) -> Cofree f a -> b

现在我们真的很专业cata用更具体的b , 即 Fix f :

-- expected type of `cata` in `forget`
cata :: Functor f => ((a, f (Fix f)) -> Fix f) -> Cofree f a -> Fix f

forget在 a 中是参数化的和 f , 所以我们给出的函数 cata对 a 无能为力在这对中，唯一明智的方法是实现剩余的 f (Fix f) -> Fix f是Fix包装器。

操作上，Fix是身份，所以(\(_ :< z) -> Fix z)真的是(\(_ :< z) -> z)这对应于删除注释的直觉，即对的第一个组件 (_ :< z) .