2

我们有一个 AST 定义：

data Term a 
  = Lam String a
  | App a a
  | Var String
  deriving(Read,Show,Eq,Functor,Foldable,Traversable)

以及用于类型推断的 F 代数：

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：

infer :: 
  (MonadState Int, MonadError TypeError) 
  => Fix Term 
  -> Result m
infer ast = cata hm ast

但是现在我希望结果是带有每个表达式的类型信息注释的原始 AST，所以现在infer' :: Fix Term -> Wrapped (Labeled Term Type)。

  1. 我应该使用什么数据结构来注释树（Cofree, Product,Fix带有自定义Label）？
  2. 如何在不修改原始w函数的情况下使用递归方案实现这一点？
4

1 回答 1

4

这个答案确实修改了 function w，但它仍然旨在使“主力”功能与递归方案机制分离。

让我们保持Term类型不变，并假设我们有一个E向下计算的环境类型，以及一个R从叶子向上计算的最终注释类型。

我们还假设我们有这两个函数：

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其用作 monad。

（请注意，我假设“计算环境”不会产生影响。我不是这种情况，那么这个解决方案不会起作用。）

我们分两个阶段工作。首先，我们构建一棵树，其中的节点已经用它们的环境进行了注释。我们使用anamorphism，而不是从 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

（请记住，type instance Base (Cofree f a) = CofreeF f a这就是 的COFREEF.:< 来源。它基本上是一对纯值和另一个包裹在函子中的值。）

在下一阶段，我们有效地从叶子中使用带注释的树来产生最终结果——带R注释的树：

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

我分两个阶段进行，因为我无法将“返回函数”技巧与返回带注释的树结合起来。

变质后跟变质被称为hylomorphism。我们可以使用 定义组合函数hylo，如下所示：

together :: E -> Fix Term -> IO (Cofree Term R)
together = curry (hylo alg coalg)
    where
    coalg (environment, Fix term) = ...
    alg (environment COFREEF.:< termio) = ...

您可以将原始代数的形式放在一起calcEnv，如下所示：calcResult

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
于 2017-09-10T17:02:13.563 回答