Transform

tl;dr: Transform your data structures recursively from the bottom up. Very useful eg. for writing compiler passes.

Inspired by various tweets and my use for something like this in my compiler project.

Let's say you're writing a compiler and have this AST data structure:

type Expr
    = Int_ Int
    | Negate Expr
    | Plus Expr Expr
    | List_ (List Expr)

You also have a few optimizations you compiler can do:

simplifyDoubleNegate : Expr -> Expr
simplifyDoubleNegate expr =
    case expr of
        Negate (Negate (Int_ int)) ->
            Int_ int

        _ ->
            expr


simplifyNegate : Expr -> Expr
simplifyNegate expr =
    case expr of
        Negate (Int_ int) ->
            Int_ (negate int)

        _ ->
            expr


simplifyPlus : Expr -> Expr
simplifyPlus expr =
    case expr of
        Plus (Int_ a) (Int_ b) ->
            Int_ (a + b)

        _ ->
            expr

And let's say we've got this AST:

ast : Expr
ast =
  List_
    [ Negate
            (Plus
                (Int_ 1)
                (Negate (Int_ 8))
            )
        , List_
            [ Negate
                (Int_ 8)
            , Plus
                (Int_ 1)
                (Negate
                    (Negate
                        (Int_ 8)
                    )
                )
            ]
        ]

Now, the burning question is, how do we run these recursively on the whole AST? How do we make sure there are no gains to be had if we run one more optimization somewhere?

This package has just what you need. Watch!

• First, we'll say how and which children we want to recurse to.
• Then, we'll combine our transformations in an (almost) order-independent way. (Well, it will be much better our way than by just composing them.)
• Then, as the last step, we'll run the transformations as long as they actually change the data structure.

{-| FIRST: say how to recurse!
-}
recurse : (Expr -> Expr) -> Expr -> Expr
recurse fn expr =
    case expr of
        Int_ int ->
            Int_ int

        Negate e ->
            Negate (fn e)

        Plus left right ->
            Plus (fn left) (fn right)

        List_ es ->
            List_ (List.map fn es)

{-| SECOND: combine the transformations!
-}
simplifyAll : Expr -> Maybe Expr
simplifyAll =
    Transform.orList_
        [ simplifyDoubleNegate
        , simplifyNegate
        , simplifyPlus
        ]

{-| THIRD: run the transformations until nothing changes anymore!
-}
simplifiedAst : Expr
simplifiedAst =
    Transform.transformAll
        recurse
        simplifyAll
        ast

The result?

simplifiedAst
--> List_ [Int_ 7, List_ [Int_ -8, Int_ 9]]

(By the way, the functions here are general enough to work on anything, not just on custom types. Feel free to use it on records, for example!)

Conceptually, this is a spiritual equivalent of Control.Lens.Plated from Haskell.

Because we don't have auto-derived lenses, it needs you to give it that recurse function.

In the future, there are other possible functions to add, like getting the immediate children or all the descendants. Let me know if those would be useful for you!