Bugs
----
Script →#.math← does a poor job of collecting "like terms":

      math script until ')'

    x+y + x+y           ⍝ good
2*(x+y)

    x+y + x+y + x+y     ⍝ not so good
2*(x+y)+x+y

    x+y+z + x+y+z       ⍝ abysmal
x+y+z+x+y+z

    )

In  general, to collect terms that are arbitrarily far apart, we would need arb-
itrarily complex reduction templates.

One solution would be to install a separate "collection" phase alongside reduce,
to do the job.

      numb──←─┐   ┌────┐   ┌────────┐   ┌─────┐
              ├─←─┤show├─←─┤evaluate├─←─┤parse├───←──expr
      expr──←─┘   └────┘   └─┬────┬─┘   └─────┘
                             ↓    ↑
                           ┌─┴────┴─┐
                           │ reduce │
                           └─┬────┬─┘
                             ↓    ↑
                           ┌─┴────┴─┐
                           │collect │
                           └────────┘

The  collector  would need to know whether each infix function is commutative or
associative. The information could be indicated either in the function declarat-
ion itself:

    ← *(×)⍨≡    /(÷)            ⍝ mul div
          │└──────────────────  associative
          └───────────────────  commutative

or by ancilliary declarations of the form:

    :commutative + *
    :associative + *

Note that the _distribution_ of functions with respect to each other (* distrib-
utes  over  +  etc) is already handled adequately by the reduction subsystem, as
distribution is a _local_ effect within the expression tree.

The  collector  would  identify like terms and try to bring them close enough in
the expression tree for the reduction rules to take effect.

    ((((x+y)+z)+x)+y)+z     ⍝ fully parenthesised starting expression.

    ((((x+y)+z)+x)+y)+z     ⍝ like terms
        ¯       ¯
    ((((x+y)+z)+x)+y)+z     ⍝ + associative
         ¯  ¯
    (((x+(y+z))+x)+y)+z     ⍝ + commutative
        ¯
    ((((y+z)+x)+x)+y)+z     ⍝ + associative
            ¯  ¯
    (((y+z)+(x+x))+y)+z     ⍝ reduction rule
             ¯¯¯
    (((y+z)+(2*x))+y)+z     ⍝ like terms
       ¯           ¯
    ...

    ((2*z)+(2*y))+(2*x)

    ...

    2*(z+x+y)


Lexicographical Ordering
-------------------------
An alternative might be to introduce a further pattern-matching mechanism, which
would allow for lexicographical ordering of expressions and thus, the collection
of like terms across commutative and associative infix functions.

In the following, let's use >> (and <<)  as short-hand for "is lexicographically
greater-than (and less-than)" and introduce new pattern-matching symbols ⍋ and ⍒
so that:

    (..⍋..⍒..)  matches  (..X..Y..)  iff  X >> Y

A reasonable choice of ordering might be:

    [1] Expressions ordered by their operator binding strengths,
    [2] Non-atomic expressions trump atoms.
    [3] Atoms sort in {⍵[⍋↑⍕¨⍵]} order.

For example, using the →##.math← script:

    a∧b >> a*b          ⍝ ∧ binds tighter than *,
    a*b >> c∧d + e∧f    ⍝ * binds tighter than +,
    x+y >> a            ⍝ expressions trump atoms,
      d << 123          ⍝ literals follow variables,
      a << b            ⍝ "a" precedes "b".

This would enable reduction rules, for commutative and associative operators, to
collect "heavier" terms to the left, in accordance with mathematical convention.
Here is an example for the commutative and associative function +:

      ⍋+⍒ = ⍒+⍋             ⍝ + is commutative:     b+a => a+b
    p+⍋+⍒ = p+⍒+⍋           ⍝ and associative:  (x+z)+y => (x+y)+z

which would tend to collect like terms:

    y + x + z + x + y + z       ⍝ ⍋+⍒ => ⍒+⍋
    ¯¯¯¯¯
→   x + y + z + x + y + z       ⍝ p+⍋+⍒ => p+⍒+⍋
          ¯¯¯¯¯¯¯
→   x + y + x + z + y + z       ⍝ p+⍋+⍒ => p+⍒+⍋
      ¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯
→   x + x + y + y + z + z       ⍝ p+p => 2*p
    ¯¯¯¯¯   ¯¯¯¯¯   ¯¯¯¯¯
→   2*x + 2*y + 2*z             ⍝ (p*q)+(p*r)  =>  p*(q+r)
    ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
→
    2*(x+y+z)

It is tempting to use this mechanism to try to arrange  expression  terms  in  a
pleasing order. We might prefer: (4*x∧2 + 3*x - 7) rather than (x*3 - 7 + x∧2*4)
and to see (x+y) instead of (y+x). This leads to a slight conundrum in that:

We like our expression variables in alphabetical order:

    x+y+z           ⍝ x << y << z

but our polynomial terms in decreasing order of exponent:

    x∧3 + x∧2       ⍝ x∧3 << x∧2:  implies 3 << 2 !

One way out of this dilema is to define the lex-ordering of variable names to be
the reverse of alphabetical ordering.

See also: →Differentiation←

Back to: →Contents