Rebuild Patterns

15 January 2023

Or-patterns are awesome, but I often run into situations where I cannot use them, so I came up with a solution.

Or-patterns are very convenient for functions that somehow deconstruct values, e.g. finding all literals in an arithmetic expression

data Expr = Literal(Int)
          | Add(Expr, Expr)
          | Sub(Expr, Expr) 

let literals(expr) = match expr {
    Literal(n) -> [n]
    Add(expr1, expr2) | Sub(expr1, expr2) ->
         literals(expr1) ++ literals(expr2)
}

But it breaks down as soon as a function is meant to rebuild the expression, for example a function that sets all literals to 0

let replaceLiterals(expr) = match expr {
    Literal(n) -> Literal(0)
    Add(expr1, expr2) | Sub(expr1, expr2) ->
        ???(replaceLiterals(expr1), replaceLiterals(expr2))
}

The ??? would need to be Add in one case and Sub in the other, but otherwise these should behave exactly the same!

My solution: rebuild patterns

let replaceLiterals(expr) = match expr {
    Literal(n) -> Literal(0)
    Add(expr1, expr2) | Sub(expr1, expr2) rebuild constructor ->
        constructor(replaceLiterals(expr1), replaceLiterals(expr2))
}

Now, patterns of the form <pattern> rebuild <name> bind name to a function that takes all variables in pattern as parameters and rebuilds it from there. In the example above, constructor is equivalent to either \expr1 expr2 -> Add(expr1, expr2) or \expr1 expr2 -> Sub(expr1, expr2), depending on the value of expr.

This also works for more complicated patterns where not every subpattern is a variable pattern, e.g.

data Expr = ...
          | If({ condition : Expr, thenBranch : Expr, elseBranch : Expr })

let replaceLeftmostLiteral(expr) = match expr {
     Literal(n) -> Literal(0)
     Add(expr, _) | Sub(expr, _) | If({ condition = expr | _ }) rebuild constructor ->
        constructor(replaceLeftmostLiteral(expr))
}

Is there some prior art on something similar to this?