What is the easiest way to update an immutable AST?

Question

While working with macros, I have reached the point (I have been trying hard to avoid it) where I need to update those nodes in the AST which hold certain condition. For instance, let's say I would like to update each node:

Literal(Constant(1))

with the value:

Literal(Constant(2))

Those AST nodes could be anywhere in the expression tree, so I cannot use an ad-hoc pattern matcher. Obviously, the last thing I would like to do is to code a full pattern matcher which is able to cover all the compiler primitives. I have been searching in the API but I have the impression that methods such as collect and the traversable family are not good enough to fulfill my needs, since they treat the tree as a linear thing, and I want the whole updated tree as a result. So, is it possible to update an immutable expression tree in a smart way? Why doesn't exist such 'update' operation in the standard API?

Answer 1

Here's an example of using an AST transformer in a Scala macro:

https://github.com/retronym/macrocosm/blob/171be7e/src/main/scala/com/github/retronym/macrocosm/Macrocosm.scala#L129

Answer 2

Modifying poly-typed nodes in data structures generically is a classic case of datatype generics (parameterization of code via type constructor).

Several approaches exist for such operations, such as the "Scrap Your Boilerplate" approach, which define datatype generic traversal functions.

In Haskell, the node update function is parameterized in two dimensions: by datatype and by code -- so you can apply different update functions to different types, anywhere in a structure:

-- | Apply a transformation everywhere in bottom-up manner
everywhere :: (forall a. Data a => a -> a)
           -> (forall a. Data a => a -> a)

Doing so in Haskell relies heavily on type classes. In Scala, there are several ported examples