ツリーを再帰的に降りて各分割時に新しいローカル状態を維持する計算をどのように表現しますか？

Question

文脈

実際にはタイトルの質問は私が持っている特定の問題のジェネリック版です。以下の一般的な質問またはこの特定の質問に自由にお答えください。

純粋な型なしラムダ計算ASTをトラバースし、変数をDe-Bruijnインデックスに置き換える関数を実装しています。 ASTの2つの表現、（変数名との）外部と内部の（と指数）があります。

type Id = String 

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

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

デ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の分割を構成し、各分割で新しい「ローカル」状態が生成されます。

質問

理想的には、私はたびAST分割を新しいローカル状態を把握し、いくつかのモナドの計算としてこれを記述したい、私の最初の試み：

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

は動作しません。すべてのブランチが同じ状態を共有し、インデックスを投げ捨てるからです。では、このように見える非常に一般的な計算パターンをどのように記述しますか？

Answer 1

あなたはReader monad transformerが必要になります。ここでは

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は、現在の環境への第一引数を適用した結果である、ローカル環境で、その計算（第2引数）を実行するので、分割後に分岐しても、同じ環境で混乱することはありません。

あなたが本当に唯一のスプリットに新しい環境を作成し、新しい変数紹介に古いものを維持したい場合にも、このような方法で、Stateモナド変圧器を使用することができます。

ここ

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) 

、代わりに結合subcomputationsの現在のモナドスレッドに分割すると、新しいモナドスレッドが生成され、現在の状態で評価されます。