Не мутирующие деревья в Haskell

Question

Я сейчас преподаю себе Haskell; скажем, исключительно ради аргумента, что я пишу компилятор в Haskell. У меня есть AST, определенный с чем-то вроде:

data Node = 
     Block { contents :: [Node], vars :: Map String Variable } 
    | VarDecl { name :: String } 
    | VarAssign { name :: String, value :: Node, var :: Variable } 
    | VarRef { name :: String, var :: Variable } 
    | Literal { value :: Int } 

Каждый Block является кадр стека. Я хочу разрешить все ссылки переменных.

В мире с изменяемыми данными, как я хотел бы сделать это:

• ходить след дерева по поддержанию самых последних Block ищет VarDecl узлов; на каждом из них я бы добавил Variable ближайшему Block.
• Прогулка по дереву, поиск VarAssign и VarRef Узлы. Каждый раз, когда я вижу один, я бы посмотрел переменную в цепочке кадров стека и аннотировал узел AST с соответствующим Variable.

Теперь, когда я делаю работу по дереву, и наткнулся на VarRef, я точно знаю, какой Variable на самом деле идет речь.

Конечно, в Haskell мне нужен другой подход из-за того, что дерево не изменчиво. Наивный подход - переписать дерево.

declareVariables Block contents _ = Block { 
    contents = declareVariables contents, 
    vars = createVariablesFor (findVariablesInBlock contents) } 
declareVariables VarAssign name value var = 
    VarAssign name (declareVariables value) var 
declareVariables Literal i = Literal i 
...etc... 

findVariablesInBlock VarDecl name = [name] 
findVariablesInBlock Block contents _ = [] 
findVariablesInBlock VarAssign name value _ = 
    findVariablesInBlock value 
...etc... 

(Весь код полностью непроверенной и чисто для иллюстративных целей.)

Но это довольно отвратительное; Я в конечном итоге хожу по дереву дважды, один раз, чтобы найти Block s и один раз, чтобы найти VarDecl s, и там очень много шаблонов. Плюс, учитывая, что Variable не изменен, существует ограниченное количество использований для аннотации всех моих узлов с одним в первую очередь. Я не могу с пользой аннотировать Variable, не переписывая все дерево снова.

Альтернатива A: Я мог бы сделать все изменчивым. Теперь у меня есть дерево STRef s, и все должно жить внутри монады ST. Как побочный эффект, мой код пахнет.

Альтернатива B: не пытайтесь хранить все в одной и той же структуре данных. Имейте полностью раздельное хранение структур StackFrame и Variable, и создавайте их, когда я иду по дереву, оставляя АСТ нетронутым. За исключением того, что это означает, что я не могу легко отобразить от VarRef до Variable, что было целым пунктом упражнения. Я мог бы создать таблицу поиска Data.Map VarRef Variable ... но это тоже ужасно.

Какой хороший способ решения Haskell-идиома решить эту проблему?

Answer 1

Возможно, что-то вроде этого (как с кодом, совершенно непроверенные и предназначены только для иллюстративных целей):

data Node var 
    = Block { contents :: [Node] } 
    | VarDecl { name :: var } 
    | VarAssign { name :: var, value :: Node } 
    | VarRef { name :: var } 
    | Literal { value :: Int } 

Идея вышеуказанного типа является то, что AST узлы параметризовано какую информацию они хранят о переменных. После простого анализа они будут хранить только имена переменных (так что имеют тип Node String); то будет фаза разрешения имен, которая преобразует их в ссылки какого-либо другого вида (так что производят тип Node Variable).Таким образом:

data GenVar a 
genVar :: String -> GenVar Variable 
genVar = undefined 

type Environment = Map String Variable 
resolveNames :: Environment -> Node String -> MaybeT GenVar (Node Variable) 
resolveNames env ast = case ast of 
    VarDecl name  -> mzero -- variable declarations serve no purpose after all variables have been resolved 
    VarAssign name value -> VarAssign <$> lookup name env <*> pure value 
    VarRef name  -> VarRef <$> lookup name env 
    Literal  value -> Literal <$>      pure value 
    Block contents -> do 
     vars <- mapM (lift . genVar) names 
     -- union is left-biased, so this will overwrite old variables 
     -- (if your language can refer to outer scopes, you will need 
     -- a more exciting environment like [Map String Variable]) 
     let env' = fromList (zip names vars) `union` env 
     Block <$> mapM (resolveNames env') stmts 
     where 
     (decls, stmts) = partition isDecl contents 
     names = map name decls 

isDecl VarDecl{} = True 
isDecl _ = False 

Я оставил часть переменного поколения, где вы поворачиваете имя переменного в какое-то более структурированное представление переменного, до вас (так как вы сказали немного о том, что вы хотите Variable типа выглядеть) , Но несколько примеров: можно было бы выбрать Variable, чтобы быть какой-то изменчивой ссылкой, а GenVar - подходящей монадией мутации; или поочередно, возможно, Variable - это просто Integer, а GenVar - это монада.