haskell 使用变形忘记树注解

ldxq2e6h  于 9个月前  发布在  其他
关注(0)|答案(1)|浏览(69)

我有一个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转换为未标记的AST:

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

这看起来像是某种变形(我使用的是Kmett的递归方案包中的定义)。

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 = ???

任何帮助弄清楚这是否真的是一个卡塔/变形,以及为什么它是/不是一些直觉将不胜感激。

rkkpypqq

rkkpypqq1#

import Data.Functor.Foldable (cata)
import Control.Comonad.Cofree (Cofree)
import Control.Comonad.Trans.Cofree as CofreeT (CofreeF(..))
import Data.Fix (Fix(..))

forget :: Functor f => Cofree f a -> Fix f
forget = cata (\(_ CofreeT.:< z) -> Fix z)

注意:注意Cofree:<是从哪里导入的。一个来自Control.Comonad.Cofree,另一个来自Control.Comonad.Trans.Cofree(作为CofreeF数据类型的一部分)。
如果从....Trans.Cofree导入Cofree,则cata看起来如下所示:

import Data.Functor.Identity (Identity(..))
import Data.Functor.Compose (Compose(..))
import Data.Functor.Foldable (cata)
import Control.Comonad.Trans.Cofree as CofreeT (Cofree, CofreeF(..))
import Data.Fix (Fix(..))

forget :: Functor f => Cofree f a -> Fix f
forget = cata (\(Compose (Identity (_ CofreeT.:< z))) -> Fix z)

说明

只看类型,我们就可以证明实现forget只有一种方法。让我们从cata的类型开始:

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

这里t ~ Cofree f aCofreeBase的类型示例给出:

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.

即花式对类型。让我们用一个实际的pair类型来代替它,以使事情更清楚:

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

现在我们用一个更具体的b,即Fix f来专门化cata

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

forgetaf中是参数化的,所以我们给予cata的函数不能对这对中的a做任何事情,实现剩余f (Fix f) -> Fix f的唯一合理方法是Fix Package 器。
在操作上,Fix是恒等式,所以(\(_ :< z) -> Fix z)实际上是(\(_ :< z) -> z),这对应于删除注解的直觉,即对(_ :< z)的第一个分量。

相关问题