Haskell:使用算法W用类型信息标记AST [英] Haskell: Labeling an AST with type information using Algorithm W
问题描述
我们有一个AST定义:
We have an AST definition:
data Term a
= Lam String a
| App a a
| Var String
deriving(Read,Show,Eq,Functor,Foldable,Traversable)
并且用于类型推断的F代数:
And an F-Algebra for the type inference:
type Wrapped m a = Enviroment -> m a
type Result m = Wrapped (Type,Substitution)
w ::
(MonadState Int, MonadError TypeError)
=> Term (Result m)
-> Result m
w term env = ...
我们可以得到运行推理的结果使用 cata
:
We can get the result of running the inference using cata
:
infer ::
(MonadState Int, MonadError TypeError)
=> Fix Term
-> Result m
infer ast = cata hm ast
但是现在我希望结果是原始AST带有每个表达式的类型信息,因此现在 infer':: Fix Term->包裹(标签术语类型)
。
But now I want the result to be the original AST annotated with type information for each expression, So now infer' :: Fix Term -> Wrapped (Labeled Term Type)
.
- 我应该使用哪种数据结构来注释树(
Cofree
,产品
,修复
和自定义标签
)? - 如何在不修改原始
w
函数的情况下使用递归方案实现此目的?
- What data structure should I use to annotate the tree (
Cofree
,Product
,Fix
with a customLabel
)? - How can I implement this using recursion schemes, without modifying the original
w
function?
推荐答案
此答案确实修改了功能 w
,但它仍然旨在使主力功能与递归方案机制分离。
This answer does modify the function w
, but it still aims to keep the "workhorse" functions disentangled from the recursion-schemes machinery.
让我们保持期限
类型保持不变,并假设我们的环境向下计算类型为 E
,类型为 R
表示从叶子向上计算的最终注释。
Let's keep the Term
type as is, and assume we have a type E
for the environment that is calculated downwards, and a type R
for the final annotation that is calculated upwards from the leaves.
我们还假定我们具有以下两个功能:
Let's also assume that we have these two functions:
calcEnv :: E -> Term x -> E -- calculates the environment which will be passed downwards
calcResult :: E -> Term R -> IO R -- effectfully calculates the result flowing upwards
我正在使用 IO
为简单起见。
I'm using IO
as the monad for simplicity.
(请注意,我假设计算环境不会产生影响。我不是这种情况,那么此解决方案将不起作用。)
(Notice that I'm assuming that "calculating the environment" can't have effects. I this isn't the case then this solution won't do.)
我们分两个阶段工作。首先,我们构建一棵树,其中的节点已用其环境注释。我们使用变形,而不是从变态返回函数的技巧。 / p>
We work in two phases. First we construct a tree in which the nodes have been annotated with their environments. We use an anamorphism, instead of the "trick" of returning a function from a catamorphism.
import qualified Control.Comonad.Trans.Cofree as COFREEF
annotate :: E -> Fix Term -> Cofree Term E
annotate = curry (ana coalg)
where
coalg :: (E, Fix Term) -> COFREEF.CofreeF Term E (E, Fix Term)
coalg (environment, Fix term) =
let environment' = calcEnv environment term
in environment COFREEF.:< fmap ((,) environment') term
(请记住类型instance Base(Cofree fa)= CofreeF fa
。 COFREEF。:<
来自。它基本上是一对纯值,
(Keep in mind that type instance Base (Cofree f a) = CofreeF f a
. That's where the COFREEF.:<
comes from. It's basically a pair of a pure value and another value wrapped in the functor.)
在下一阶段,我们有效地从叶子中消费了带注释的树,以产生最终结果-带有<$ c $的树c> R 注释:
And in the next phase we effectfully consume the annotated tree from the leaves to produce the final result —a tree with R
annotations:
calculate :: Cofree Term E -> IO (Cofree Term R)
calculate = cata alg
where
alg :: COFREEF.CofreeF Term E (IO (Cofree Term R)) -> IO (Cofree Term R)
alg (environment COFREEF.:< termio) = do
term :: Term (Cofree Term R) <- sequenceA termio
result :: R <- calcResult environment (fmap extract term)
return $ result :< term
我做了两个阶段,因为我在将返回函数的技巧与返回结合起来时遇到困难
I did in two phases because I was having trouble combining the "returning a function" trick with returning an annotated tree.
先变形后变形的被称为同胚。我们可以使用 hylo
,像这样:
An anamorphism followed by a catamorphism is known as hylomorphism. We could define the composed function using hylo
, like this:
together :: E -> Fix Term -> IO (Cofree Term R)
together = curry (hylo alg coalg)
where
coalg (environment, Fix term) = ...
alg (environment COFREEF.:< termio) = ...
您可以放在一起 calcEnv
和 calcResult
的原始代数形式如下:
You can put together calcEnv
and calcResult
in the form of the original algebra like this:
w :: Term (E -> IO R) -> E -> IO R
w term environment = do
let downwards = calcEnv environment term
tr :: Term R <- sequenceA $ fmap ($ downwards) term
calcResult environment tr
这篇关于Haskell:使用算法W用类型信息标记AST的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!