Apply function to substructures automatically

Question

Suppose I write a "replacement" function by the type of tree of abstract syntax:

data Term = Id String | If Term Term Term | Let String Term Term ... subst :: String -- name of identifier to replace -> Term -- term to replace the identifier with -> Term -- body in which to perform the replacements -> Term subst identifier term = go where go (Id id') = if identifier == id' then term else Id id' go (If t1 t2 t3) = If (go t1) (go t2) (go t3) go (Let id' term' body) = Let id' (go term') (go body) ... 

(Ignore shadow copy problems). Notice how tedious it is to write an If branch. I have to match the pattern by naming 3 parts, and then restore If applying go to each of the three parts explicitly. For Let I need to match the correspondence, name 3 parts and restore Let applying go to the corresponding two parts explicitly. Is there an easier way (point? Free?) To write this without indicating every detail?

Answer 1

The best approach here is to use data type programming that has been precisely designed for tasks like AST. Here is an example using the standard SYB library:

 {-# LANGUAGE DeriveDataTypeable #-} import Data.Generics data Term = Id String | If Term Term Term | Let String Term Term deriving (Eq, Show, Typeable, Data) subst :: String -- name of identifier to replace -> Term -- term to replace the identifier with -> Term -- body in which to perform the replacements -> Term subst identifier term = everywhere (mkT go) where go (Id id') = if identifier == id' then term else Id id' go x = x 

This directly expresses that the transformation (in this case, applying the go function to any child of the Term type) should be applied to the whole tree from bottom to top. Not only is this much more concise, but the same code continues to work regardless of how many constructs are added to Term if the main recursion scheme remains the same.