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).

1. 我应该使用哪种数据结构来注释树（ Cofree ，产品，修复和自定义标签）？


2. 如何在不修改原始 w 函数的情况下使用递归方案实现此目的？

1. What data structure should I use to annotate the tree (Cofree,Product,Fix with a custom Label)?
2. 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屋！