Apply a function to substructures automatically
-
27-04-2021 - |
Question
Suppose I am writing a "substitute" function on an abstract syntax tree data type:
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 shadowing issues). Notice how tedious it is to write the If
branch. I have to pattern match, naming the 3 parts, and then reconstruct an If
applying go
to each of the 3 parts explicitly. For the Let
, I have to pattern match, naming the 3 parts, and reconstruct a Let
applying go
to the relevant 2 parts explicitly. Is there an easier (pointfree?) way to write this without having to spell out every detail?
Solution
The best approach here is to use datatype-generic programming, which was precisely designed for AST-walking tasks like this. Here's 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 function go
to any child of type Term
) should be applied to the whole tree in a bottom-up manner. Not only is this much more concise, but the same code continues to work no matter how many constructs are added to Term
, so long as the basic recursion scheme stays the same.