Using maxima, pattern matching, partitioning of sum, product, etc.

Richard Hennessy wrote:
> I don't think it is a warning at all.  It is an informational message stating that you are breaking a sum into two mutually 
> exclusive terms.  In this case constant terms from nonconstant terms like
>
> declare([a,b,c],constant);
>
> (a+b+c+5*a) + (x)
>
> aa gets the first term and xx gets x.  But I noticed they do not have to be always mutually exclusive, either way you get the 
> message.
>
> Rich
>
>   
<snip>

You do not give enough information to reproduce what you are doing,  so 
some of this is a guess.

declare([a,b,c],constant);
matchdeclare(aa,constantp) ; /*my guess for the rest of this */

defmatch(m1,aa+xx);   /*define a matching program */
m1(3+x); --> false

m1(3+xx) -->   [aa=3]
m1(a+b+c+xx)--> [aa=c+b+a]
/* how about if we want to match xx against x?
matchdeclare(xx,true);
defmatch(m2,aa+xx);   ===> xx+aa partitions sum  ....
/*note, at this point you may believe that all the constants will be 
absorbed in aa  and everything else in xx */

m2(a+b+c+x) ==>   [xx=x+c+b+a, aa=0].   /* This is perfectly right, but 
not what is intended */

/*Here is a fix, and shows how Robert's program CAN work, and maybe you 
are doing such a thing */
matchdeclare(xx,lambda([r],if constantp(r) then false else true));   /* 
declare xx to be a NON constant */

defmatch(m3,aa+xx)  ===> xx+aa partitions sum ...   /* not a bug in this 
case */
m3(a+b+c+x) ==> [aa=c+b+a, xx=x].

Note that the matching program has no way of telling that the two 
predicates are mutually exclusive.

Mathematica has a pattern matcher with backtracking and notations for 
patterns in which a pattern variable can be used to absorb "whatever 
else is not matched" in 3 variants. Maxima's pattern matcher does not do 
this. Part of the notion is that Maxima's pattern matcher does not have 
the potential for exponential-time blowup on backtracking, and therefore 
would be faster.  Whether this makes the system more usable or not is 
debatable. It has been shown (e.g. here) to be hard for a user to define 
and use matching patterns.  We could add a Mathematica-style pattern 
matcher to Maxima (there is one that I
wrote, in Lisp, posted;  it does not use Maxima syntax and has a 
modified internal form, though). I think it is easier to use, but except 
in rather simple cases, has hard to understand consequences.

   .........................................
So how should one write a pattern and replacement that looks like this...

f( a+b+.....+z) ==>   g({q | q in a..z and pred(q) is true} ,   {q | all 
other elements of a...z}) ?

We can write a program that does the essential work like this:

partition_sum(E,pred, action):=block([yes:0,no:0], map(lambda([r], if 
apply(pred,[r]) then yes:yes+r else no:no+r), E), apply(action ,[yes,no]));

for example,
partition_sum(a+b+c+x+z,constantp,g)   ===>   g(a+b+c, x+z).

Other versions of this could, instead of adding together pieces, could 
multiply them etc.  For example [here I've taken some liberties 
regarding binding
of names, so I don't need to use apply so much, which takes up room.  
pred(a) instead of the safer apply(pred,[a]).

partition_expr(E,pred, action, 
combiner,emptyval):=block([yes:emptyval,no:emptyval],
     map(lambda([r], if pred(r) then yes:combiner(r,yes) else 
no:combiner(r,yes), E),
    action ,[yes,no]));

to partition a product, P, we could do

partition_expr(P, constantp, g, "*",1);

  How about using the partition programs in tellsimp etc?

previously you did something like..

tellsimp(foo(aa+xx), g(aa,xx));

now you could do something like this (I'm not entirely happy with 
passing the result as a global variable, but for a way around, see later.)



(partition_sum(E,pred, action):=
    block([yes:0,no:0],
           map(lambda([r], if pred(r) then yes:yes+r else no:no+r), E),
           ANS:action (yes,no),
           true),  /* return true if pattern match succeeds */
matchdeclare (pp, lambda([r],partition_sum(r,constantp,g))),

tellsimp(foo(pp),ANS));

Of course this looks like a lot of work, this first time.  But 
partition_sum is re-useable, and if you need another rule, you end up 
doing this...

matchdeclare(qq , lambda([r],  ... setup partition);
tellsimp(bar(qq), ANS).



Anyway, this is the kind of thing I suggest you do to avoid making the 
matching program partition sums and products. One way to kludge up the 
"ANS" business is this way:

(partition_sum(E,pred, action,res):=
    block([yes:0,no:0],
           map(lambda([r], if pred(r) then yes:yes+r else no:no+r), E),
           res :: action (yes,no),   /* result stored as requested */
           true),
matchdeclare (pp, lambda([r],partition_sum(r,constantp,g,'ANS))),
tellsimp(foo(pp),ANS));

oh, one last complication:  you might want partition_sum to return false 
in case it is applied to something that is not a sum, at all.

(partition_sum_only(E,pred, action,res):=
    block([yes:0,no:0],
   if (not(atom(E)) and op(E)="+")  then
           (map(lambda([r], if pred(r) then yes:yes+r else no:no+r), E),
           res :: action (yes,no),   /* result stored as requested */
           true)
     else false),
matchdeclare (pp, lambda([r],partition_sum_only(r,constantp,g,'ANS))),
tellsimp(foo(pp),ANS));

Using this last construction we get

foo(a+%pi,x) ==> g(a+%pi,x)
foo(w) ==> foo(w)

RJF