How to get FullSimplify to fully simplify my expression with custom complexity function?

Question

To simplify based on the visual complexity of an expression (i.e. the complexity of the function as displayed in the notebook instead of the internal form, which in some cases may be substantially different), I've defined the following complexity function:

VisualComplexity:=(Count[ToBoxes[#], Except[" "|"("|")", _String], Infinity]&)

This works well on some simple examples, however not on the following:

FullSimplify[(-1+a)(-1+b) + Abs[c]^2 - Abs[d]^2,
             ComplexityFunction->VisualComplexity]
(*
==> 1 - a - b + a*b + Abs[c]^2 - Abs[d]^2
*)

What I had expected (and desired) would have been (1-a)(1-b) + Abs[c]^2 - Abs[d]^2. Note that with the built-in complexity function, it converts (1-a)(1-b) to (-1+a)(-1+b) in that context, so transforming between those two forms is definitely in the capabilities of FullSimplify.

Now my first thought was that maybe that's really less complex according to my complexity function (which would have meant tweaking that function). However, it turned out that the desired form indeed is computed to be less complex:

VisualComplexity /@ {1 - a - b + a*b + Abs[c]^2 - Abs[d]^2,
                     (1-a)(1-b) + Abs[c]^2 - Abs[d]^2}
(*
==> {20, 18}
*)

Therefore my question is: How do I get FullSimplify to generate the simpler form?

Answer 1

We can confirm that the desired form never gets tried, by viewing the expressions sent to the ComplexityFunction with Sow and Reap:

vc := (Count[ToBoxes[Sow@#], Except[" " | "(" | ")", _String], Infinity]) &

Union@Reap[FullSimplify[(-1 + a) (-1 + b), ComplexityFunction -> vc]][[2, 1]]
(*  {-1 + a, -1 + b, (-1 + a) (-1 + b), 1 - a + (-1 + a) b, 1 - a - b + a b}  *)

Therefore it seems that it will be essential to add to TransformationFunctions. First I tried generalising from the specific case given in your comment:

tf = {Automatic, # /. (x_ + a__) (y_ + b__) :> (-x - a) (-y - b) &};
SetOptions[FullSimplify, ComplexityFunction -> vc, TransformationFunctions -> tf];

FullSimplify[expr]
(*  (1 - a) (1 - b)  *)

Unfortunately this fails in certain cases, because ReplaceAll makes the first replacement it finds, which might happen to be one that doesn't decrease the complexity measure:

(* this doesn't work *)
FullSimplify[(a - b) (-1 + c) (-1 + d)]
(*  (a - b) (-1 + c) (-1 + d)  *)

(* but this does *)
FullSimplify[(-1 + c) (-1 + d) (e-f)]
(*  (1 - c) (1 - d) (e - f)  *)

Since it is problematic to find the correct pairs of terms to negate, my next approach was to convert all forms like (-1+a) into -(1-a), but in such a way that the complexity function would ignore the overall multiplier of -1 (and therefore prefer the latter form).

tf = {Automatic, $minusone (-#) &};
vc := (Count[ToBoxes[#], Except["$minusone" | " " | "(" | ")", _String], Infinity]) &
$minusone /: $minusone^2 = 1;
$minusone /: x_ + $minusone = x - 1;

specialSimplify[x_] := 
FullSimplify[x, ComplexityFunction -> vc, TransformationFunctions -> tf] /. $minusone -> -1

specialSimplify tries negating expressions and tests whether this decreases their complexity measure. The overall sign of the expression is kept correct by the symbol $minusone which is ignored by the complexity function. $minusone squared is converted to 1, and $minusone when it appears as part of a sum is converted back to -1. Any residual $minusone at the end of the simplification is converted back to -1.

This seems to well enough on toy examples, though I haven't tested it thoroughly. Note that in the last example specialSimplify prefers to have an overall minus sign than an expression like (-a+b)

specialSimplify[(-1 + a) (-1 + b)]
(*  (1 - a) (1 - b)  *)

specialSimplify[(a - b) (-1 + c) (-1 + d)]
(*  (a - b) (1 - c) (1 - d)  *)

specialSimplify[(b - a) (-1 + c) (-1 + d)]
(*  -(a - b) (1 - c) (1 - d)  *)