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(..., ...), ...).