A question about the patterns and substitution

Question

Hi friends!

In the technical manual of the Cadabra at

http://cadabra.phi-sci.com/cadabra.pdf

there is an example in the take_section and comparing its result with substitute, as follow

A + B D G + C D A;
@substitute!(%)( D Q?? -> 1);
A + G + A;

I wonder myself why the result isn't A+B+C. In the command, the pattern Q?? appears after D so why does the substitute take the previous symbols? How can I get the result A+B+C?

Best Regards!

P/S: @admin, the link to the technical manual in the new website doesn't work. I mean http://cadabra.science/cadabra.pdf

Answer 1

I will discuss how this works in 2.x, as the 1.x system is not equivalent, but more thought has gone into 2.x and that is anyway where the development is going on.

When you use substitute to replace a product, the algorithm will try to find the factors in that product one by one. If you do

 ex:= A + B D G + C D A;
 substitute(_, $D Q?? -> 1);

what happens on the 2nd term is that first the D is found, and then the algorithm starts from the beginning of the BDG term to find another object matching Q??. Starting from the first factor in BDG, it finds B, which matches the pattern Q??. The result for the 2nd term is thus G (and not B). For the 3rd term, the logic is the same. Final result:

A + G + A

which gets collected to 2A. This is what people call a 'greedy' algorithm.

Things are of course different if the symbols do not commute. If you had done (before the substitute)

{A,B,C,D,G}::NonCommuting;

then the result would indeed be

A + B + C

because the D Q?? sub-product now only matches D G, not B D.

For take_match, the logic is that any term for which the pattern matches will be kept, so with the same expression and substitute replaced with take_match, you get instead

B D G + C D A

This is perhaps not entirely satisfactory; better would be to have a notation for 'match any number of factors in a product'. This is on my list of things to improve.

Comments

This a great advise! Thank you Kasper.