我有一个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 = ???
任何帮助弄清楚这是否真的是一个卡塔/变形,以及为什么它是/不是一些直觉将不胜感激。
1条答案
按热度按时间rkkpypqq1#
注意:注意
Cofree
和:<
是从哪里导入的。一个来自Control.Comonad.Cofree
,另一个来自Control.Comonad.Trans.Cofree
(作为CofreeF
数据类型的一部分)。如果从
....Trans.Cofree
导入Cofree
,则cata
看起来如下所示:说明
只看类型,我们就可以证明实现
forget
只有一种方法。让我们从cata
的类型开始:这里
t ~ Cofree f a
和Cofree
的Base
的类型示例给出:其中
CofreeF
是:即花式对类型。让我们用一个实际的pair类型来代替它,以使事情更清楚:
现在我们用一个更具体的
b
,即Fix f
来专门化cata
:forget
在a
和f
中是参数化的,所以我们给予cata
的函数不能对这对中的a
做任何事情,实现剩余f (Fix f) -> Fix f
的唯一合理方法是Fix
Package 器。在操作上,
Fix
是恒等式,所以(\(_ :< z) -> Fix z)
实际上是(\(_ :< z) -> z)
,这对应于删除注解的直觉,即对(_ :< z)
的第一个分量。