如何表达递归下降树并在每次拆分时保持新的本地状态的计算？

Question

上下文

标题中的问题实际上是我遇到的特定问题的通用版本.请随意回答下面的一般问题或这个具体问题.

我正在实现一些遍历纯无类型lambda演算AST并用De-Bruijn索引替换变量的函数.AST有两种表示形式,外部(带有变量名称)和内部(带索引):

type Id = String

data TermEx                         
    = VarE Id                       
    | LamE Id TermEx                
    | AppE TermEx TermEx            

data TermIn                         
    = VarI Int                  
    | LamI TermIn               
    | AppI TermIn TermIn        

关于De-Bruijn索引的工作方式的快速回顾,请参见本pdf的第6页:

http://ttic.uchicago.edu/~pl/classes/CMSC336-Winter08/lectures/lec4.pdf

现行解决方案

一个定期的递归函数,可以实现我想要的:

encode' :: TermEx -> TermIn
encode' = go [] where
go en te = case te of 
    VarE x   -> case elemIndex x en of 
        Just i -> VarI 
    LamE x t  -> LamI $ go (x:en) t
    AppE t t' -> AppI (go en t) (go en t')    -- * see comment below

注释:注释函数应用程序AppI构成AST中的分割,并且在每次分割时,产生新的"本地"状态.

题

理想情况下,我想将此描述为一些monadic计算,每次AST分裂时都会跟踪一个新的本地状态,这是我的第一次尝试:

type DeBruijn = forall m. (Monad m, Functor m) => StateT [Id] m TermIn

不起作用,因为所有分支将共享相同的状态,抛弃索引.那么你如何描述这种看似非常常见的计算模式呢？

Answer 1

你需要Reader monad变换器:

import Control.Monad.Trans.Reader
import Control.Applicative
import Data.Maybe
import Data.List

type DeBruijnT = ReaderT [Id]

encode :: (Applicative m, Monad m) => TermEx -> DeBrujinT m TermIn
encode t = case t of
  VarE x    -> reader (maybe (error "!") VarI . elemIndex x)
  LamE x t  -> withReaderT (x:) $ LamI <$> encode t
  AppE t t' -> AppI <$> encode t <*> encode t'

这里,withReaderT在本地环境中执行其计算(2nd arg),这是将1st arg应用于当前环境的结果,因此,当在分割后在分支中引入新绑定时,它们不会在同一环境中陷入混乱.

此外,如果您确实只想在拆分时创建新环境,并在新变量引入上保留旧环境,则可以使用State monad转换器:

type DeBruijnT = StateT [Id]

encode :: (Applicative m, Monad m) => TermEx -> DeBruijnT m TermIn
encode t = case t of
  VarE x    -> gets (maybe (error "!") VarI . elemIndex x)
  LamE x t  -> withStateT (x:) $ LamI <$> encode t
  AppE t t' -> do
    s <- get
    AppI <$> lift (evalStateT (encode t ) s)
         <*> lift (evalStateT (encode t') s)

这里,不是将分割上的子计算绑定到当前的monadic线程,而是生成新的monadic线程并使用当前状态进行评估.