Commutative Pattern Matching

I am currently working on building a simplifier for mathematical expressions. I want to find a way to match certain cases commutatively while still being able to bind values in patterns.

So... for a bit more insight into my problem.

I have an Expression enum:

enum Expression {
    indirect case add(Expression, Expression)
    indirect case subtract(Expression, Expression)
    indirect case multiply(Expression, Expression)
    indirect case divide(Expression, Expression)
    indirect case power(Expression, Expression)
    indirect case log(Expression, Expression)
    case x
    case n(Int)
}

extension Expression: Equatable {
    static func == (lhs: Expression, rhs: Expression) -> Bool {
        switch (lhs, rhs) {
        case let (.add(a, b), .add(c, d)) where a == c && b == d,
             let (.subtract(a, b), .subtract(c, d)) where a == c && b == d,
             let (.multiply(a, b), .multiply(c, d)) where a == c && b == d,
             let (.divide(a, b), .divide(c, d)) where a == c && b == d,
             let (.power(a, b), .power(c, d)) where a == c && b == d,
             let (.log(a, b), .log(c, d)) where a == c && b == d:
            return true
        case let (.n(a), .n(b)) where a == b:
            return true
        case (.x, .x):
            return true
        default:
            return false
        }
    }
}

I perform a lot of pattern matching on my Expression type. The commutativity of addition and multiplication would really help me to do things like collect like terms and also greatly reduce the quantity of cases I need to write.
For example, it would shorten:

case let .multiply(.add(a, b), .add(c, .log)),
     let .multiply(.add(a, b), .add(.log, c))
     let .multiply(.add(c, .log), .add(a, b)),
     let .multiply(.add(.log, c), .add(a, b)): //...

With:

case let .multiply(.add(a, b), .add(c, .log)): //...

First Attempt

I wanted to find a way to simplify and shorten all of my commutative cases, so I decided to make an ExpressionPattern enum and define an overload of the pattern matching operator ( ~= ).

enum ExpressionPattern {
    case commutativeMultiply(Expression, Expression)
    case commutativeAdd(Expression, Expression)
}

func ~= (lhs: ExpressionPattern, rhs: Expression) -> Bool {
    switch lhs {
    case let .commutativeMultiply(a, b):
        switch rhs {
        case .multiply(a, b), .multiply(b, a):
            return true
        default:
            return false
        }

    case let .commutativeAdd(a, b):
        switch rhs {
        case .add(a, b), .add(b, a):
            return true
        default:
            return false
        }
    default:
        return false
    }
}

I want to be able to replace pattern matching statements like:

case let .add(.n(3), a), let .add(a, .n(3)) where a > 10: //matches (a + 3), (3 + a)
//...

With:

case let .commutativeAdd(.n(3), a) where a > 10: //matches (a + 3), (3 + a)
//...

When I tried to do this for the first time though, I got an error say "Pattern variable binding cannot appear in an expression".

Note: I am aware that this match works if I use the exact, final values without value binding, but I utilize this feature in many places throughout my project so it is sort of a necessity for me.

Usage Attempt:

let expression: Expression = Expression.add(.divide(.n(1), .n(2)), .subtract(.n(3), .n(4)))
switch expression {

case let .commutativeAdd(.subtract(a, b), .divide(c, d)): //Error: Pattern variable binding cannot appear in an expression.
    print("This matches: ((\(a) - \(b)) + (\(c) ÷ \(d))) and ((\(c) ÷ \(d) + (\(a) - \(b)))")

default: 
   break

}

Not deterred, I decided to try again and make some changes to Expression itself to make it pattern match commutatively without any helper enum or anything. Changing how Expression itself inherently behaves is more useful/easier to use anyways.

Second Attempt

For my second attempt I changed the definition of Expression 's == function, and tried to override its default implementation of ~= .

extension Expression: Equatable {
    static func == (lhs: Expression, rhs: Expression) -> Bool {
        switch (lhs, rhs) {
        case let (.add(a, b), .add(c, d)) where  (a == c && b == d) || (a == d && b == c),
             let (.subtract(a, b), .subtract(c, d)) where a == c && b == d,
             let (.multiply(a, b), .multiply(c, d)) where  (a == c && b == d) || (a == d && b == c),
             let (.divide(a, b), .divide(c, d)) where a == c && b == d,
             let (.power(a, b), .power(c, d)) where a == c && b == d,
             let (.log(a, b), .log(c, d)) where a == c && b == d,
             let (.root(a, b), .root(c, d)) where a == c && b == d:
            return true
        case let (.n(a), .n(b)) where a == b:
            return true
        case (.x, .x):
            return true
        default:
            return false
        }
    }

    static func ~= (lhs: Expression, rhs: Expression) -> Bool {
        return lhs == rhs
    }
}

Usage Attempt:

let expression: Expression = Expression.add(.divide(.n(1), .n(2)), .subtract(.n(3), .n(4)))
print(expression == .add(.subtract(.n(3), .n(4)), .divide(.n(1), .n(2)))) //Prints "true"

switch expression {
case let .add(.subtract(.n(a), .n(4)), .divide(.n(1), .n(2))):
    print("Matched")
default:
    print("Not matched")
}

//Prints "Not matched"

Note: This should have ideally printed "Matched".


Question

How do I find a way to use full-fledged pattern matching (value binding and all) while taking into account commutativity of certain cases?

Note: This must be able to be used for matching nested cases with commutativity (i.e. .add(.multiply(..., ...), ...) ). This is especially important as a lot more cases are needed when matching something with both addition and multiplication. Also, doing an operation like checking for terms you can combine become much easier to perform with commutative cases like: .add(.add(..., ...), ...).

Not exactly an answer to your question but I was doing something similar and took a different approach. I added an extra (recursive) step to normalize expressions. I think the problem becomes a lot more tractable once you can make assumptions about the order of the terms that you have enforced in a previous step. (eg: if there's an addition numeric values come first sorted by size, then log expressions etc.).

Edit: Also you can make your life much easier by defining +, -, * and extending CustomIntConvertible so you can change things like this:

let expression: Expression = Expression.add(.divide(.n(1), .n(2)), .subtract(.n(3), .n(4)))

to:

let expression: Expression = 1/2 + (3-4)

You can use that kind of syntax inside switch statements too (for example in the normalize function, or if you add one to simplify expressions).

3 Likes

I, too, would like to be able to specify custom binding pattern
matches. It's not something that Swift supports. I haven't found
anything under the evolution process, but maybe there is something I
have overlooked.

File under "philosophical questions": what is the type of
.multiply(let a, .n(3)) ? Does the compiler have to synthesize the
type? Do we need to indicate a protocol conformance to force that
synthesis?

What do you think about matches like the following?

case "Hello, my name is \(let name)":
	/* ... statement using `name` ... */

Dave

1 Like

I, too, would like to be able to specify custom binding pattern
matches. It's not something that Swift supports. I haven't found
anything under the evolution process, but maybe there is something I
have overlooked.

File under "philosophical questions": what is the type of
.multiply(let a, .n(3)) ? Does the compiler have to synthesize the
type? Do we need to indicate a protocol conformance to force that
synthesis?

What do you think about matches like the following?

case "Hello, my name is \(let name)":
        /* ... statement using `name` ... */

Dave

Would it be better if the associated types are sequences instead?

indirect case add(UnorderedArgs<Expression>)

You can then declare UnorderedArgs<E> to be ExpressibleByArrayLiteral

Terms of Service

Privacy Policy

Cookie Policy