Expression.equals fails sometimes, expandAndSimplify is the culprit

[MatthewJA]

var expr = CQ("a*x**3 - b = 0");
var sol = expr.solve("x");
sol[0].equals(CQ("(b/a)**(1/3)")); // false
sol[0].simplify().equals(CQ("(b/a)**(1/3)")); // true

So @expr.expandAndSimplify isn't fully simplifying. I'm not really sure why, but one possible (bad?) solution is to just keep simplifying until the expression no longer changes.

[zvxryb]

I'm not so sure that simplification is the right way to go about this, I just used what I had available. Maybe it should just expand instead? Distribute all power/multiplication terms so the expression tree is always (from top to bottom) "addtion > multiplication > power", then sort all terms so that you have a fully unambiguous canonical form.

[MatthewJA]

I think you're right, expanding makes sense. I'm not entirely sure expanding is going to give a canonical form, though (which seems to be the problem here anyway), so that'll need to be fixed. The simple solution is to call expand until the expression no longer changes, but that's pretty slow.

[zvxryb]

I started experimenting with writing a canonicalization function on this branch. It still needs work. There is currently an issue with distribution of division, which I find odd, because distribution of powers appears to work OK and division is just multiplication by Pow(base, -1).

My approach, so far, is as follows:

• All operators have a canonical class method which applies the operation while enforcing canonicalization rules.
  • Inputs are required to be in canonical form. This is guaranteed by the canonicalize instance method, which canonicalizes sub-expressions before canonicalizing the current expression.
  • Output of a given operator's canonical is not necessarily a node of that operator's type. An example of this is that Mul.canonical will return an Add node if the multiplication is distributed over an Add operand.
• Rules
  • Generally Add > Mul > Pow, with special cases for exponents
  • Add and Mul must have at least two terms (not including identities 0 or 1, respectively)
  • Add may not contain another Add (combine terms)
  • Mul may not contain another Mul (combine terms)
  • Mul may not contain Add (distribute)
  • Base of Pow may not be another Pow (combine exponents)
  • Base of Pow may not be a Mul (distribute)
  • Exponent of Pow may not be an Add (distribute)
• Add.canonical
  • Combine terms with Add operands
  • Collect like terms with Mul.canonical
  • If no terms remain, return Constant(0)
  • If one term remains, return that term
• Mul.canonical
  • Combine terms with Mul operands
  • Distribute over Add, return result
  • Collect terms with similar bases using Pow.canonical
  • If no terms remain, return Constant(1)
  • If one term remains, return that term
• Pow.canonical
  • If constant exponent is 1, return base
  • If exponent is an Add, split the terms. Multiply individual powers for each term in the exponent.
  • If base is an Add and exponent is a Constant
  • Multiply base n times, where n is the integer part of the exponent
  • Multiply a new Pow for the fractional part of the exponent
  • Distribute over Mul
  • If base is Pow, multiply exponents

Also, although I wrote a separate implementation, I think there is some overlap between canonicalize and simplify (distribution, collection of like terms, etc.). As I see it, canonicalize is focused on unambiguous results, while simplify focuses on producing concise human-readable results. I think this makes simplify a superset of canonicalize which performs additional simplification, not necessarily respecting the above constraints.

[MatthewJA]

That looks really good! I'd definitely expect overlap between canonicalize and simplify, but possibly more overlap with expand. One idea that comes to mind is rewriting simplify and expand in terms of canonicalize, which I think makes a great deal more sense than the existing implementations of simplify and expand, so I might do that once.

But yeah, looks great so far!