design - Not mutating trees in Haskell -

i'm teaching myself haskell; let say, purely sake of argument, i'm writing compiler in haskell. have ast, defined like:

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 } 

each block stack frame. wish resolve variable references.

in world mutable data, way i'd is:

• walk tree keeping track of recent block looking vardecl nodes; @ each one, i'd add variable closest block.
• walk tree again, looking varassign , varref nodes. each time see one, i'd variable in stack frame chain , annotate ast node corresponding variable.

now, whenever i'm doing work on tree, , come across varref, know precisely variable being referred to.

of course, in haskell i'd need different approach, due tree not being mutable. naive approach rewrite tree.

declarevariables block contents _ = block {     contents = declarevariables contents,     vars = createvariablesfor (findvariablesinblock contents) } declarevariables varassign name value var =     varassign name (declarevariables value) var declarevariables literal = literal ...etc...  findvariablesinblock vardecl name = [name] findvariablesinblock block contents _ = [] findvariablesinblock varassign name value _ =     findvariablesinblock value ...etc... 

(all code untested , purely illustrative purposes.)

but pretty gruesome; end walking tree twice, once find blocks , once find vardecls, , there's awful lot of boilerplate. plus, given variable isn't mutable, there's limited amount of use annotating nodes 1 in first place --- can't usefully annotate variable without rewriting whole tree again.

alternative a: make mutable. i've got tree of strefs , has live inside st monad. side effect, code smells.

alternative b: don't try store in same data structure. have separate storage of stackframe , variable structures, , build these when walk tree, leaving ast untouched. except means can't map varref variable, whole point of exercise. create data.map varref variable lookup table... that's gruesome, too.

what's haskell-idiom way of solving kind of problem?

perhaps (as code, untested , intended illustrative purposes):

data node var     = block { contents :: [node] }     | vardecl { name :: var }     | varassign { name :: var, value :: node }     | varref { name :: var }     | literal { value :: int } 

the idea of above type ast nodes parameterized information store variables. after mere parse, store variable names (so have type node string); there name resolution phase converts them references of other kind (so produce type node variable). thus:

data genvar 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 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 ->         vars <- mapm (lift . genvar) names         -- union left-biased, overwrite old variables         -- (if language can refer outer scopes, need         -- more exciting environment [map string variable])         let env' = fromlist (zip names vars) `union` env         block <$> mapm (resolvenames env') stmts                 (decls, stmts) = partition isdecl contents         names = map name decls  isdecl vardecl{} = true isdecl _ = false 

i left variable generation part, turn variable name more structured representation of variable, (since said little want variable type like). few examples: 1 might choose variable kind of mutable reference, , genvar suitable mutability monad; or alternately perhaps variable integer , genvar supply monad.