Rewrite multiply

[joshuabowers]

As of monadic, multiply is a mess: attempts were made to unroll a mutually recursive set of algorithms introduced in functional to handle nested edge cases, but the result is cumbersome and could use refinement.

There exist some (fairly easy to trip) edge cases which are demonstrably unsupported by monadic's implementation which should be handled. For example, something like the following pathological case would not be properly rewritten:

(x*(y*(z*(w*x))))

Despite there being two x variables which, due to the rules of associativity and commutativity of multiplication, could be condensed into an x**2, GraphCa would likely not notice that arrangement in monadic.

Figuring out a recursive algorithm that is easier to reason about than functional's is desirable; attempting to unroll such an algorithm, as in monadic, is untenable.

[joshuabowers]

Several steps will need to be taken to make multiply---as well as, I'm fairly certain, add---better, in both design and behavior.

1) Introduce a new binary utility function, which is responsible for walking a TreeNode, cleaving it along a given species, and emitting the results to the calling context. Such a function would only recurse over the given species type, but would essentially generate an array of all descendants which effectively are siblings under the rules of associativity and commutativity for the species operation. Something like the following:

export const walk = (species: Species) => {
  function *cleave(node: Writer<TreeNode>){
    if(node.species === species){
      yield *cleave(node.left)
      yield *cleave(node.right)
    } else {
      yield node
    }
  }
  return cleave
}

Some extra logic likely needed to make that fully type-safe. Point: walk transforms a series of nested self-similar binary node constructs into a list of operands that can be commuted and associated.

2) Introduce a sibling function to the when functions: otherwise; these would be intended to be an operation of last result to handle any edge case that hasn't been handled. otherwise behaves like---and essentially wraps---a method without a case function. unary/binary could potentially be updated to accept otherwise in the extensions block via something like:

type OtherwiseFn = /* ... */
type WhenFn = /* ... */
type ExtensionFns = WhenFn | WhenFn[] | OtherwiseFn | [...WhenFn[], OtherwiseFn]

Though, again, that might need some tweaking. But that should allow an otherwise block to be optionally present once and only once, and, if present, always as the last argument.

3) Using otherwise, multiply could condense most of its current behavior into this last resort block, wherein it would use walk on both children to get a list of multiplicands that are associative and commutative. Then, a series of list operations could be performed to iteratively mutate this multiplicands list; should an iteration occur without modification, the otherwise block is complete and returns the results. A vague prototype would look like:

const mWalk = walk(Species.multiply)

export const multiply = binary(...)(...
  otherwise((l, r) => {
    // l, r are Writer<TreeNode>
    let multiplicands = [...mWalk(l), ...mWalk(r)]
    let changed = true
    while(changed){
      changed = false
      const primitives = multiplicands.find(isPrimitive)
      const reduced = primitives.reduce((a, i) => multiply(a, i))
      changed = primitives.length !== reduced.length
      multiplicands = [...reduced, ...multiplicands.filter(m => !isPrimitive(m))]
      // Extra steps, as above, for handling variables and exponentiations.
      // Multiple loops to account for situations like x * x^-1 => 1
    }
  })
)

The real trick here would be attempting to make the logging for this process make sense.

Conclusion) The above should result in a demonstrably shorter multiply, albeit one that has much more robust behavior. Faster? Unknown. The otherwise block should take care of a number of edge cases automatically (assuming checks are performed for 0, Infinity, etc).

Note: method's of last resort prevent any further processing, which would be problematic with how binary currently adds functions to the system. There might need to be some special casing to allow an otherwise block to utilize the edge cases defined by binary, but also allow the default case for creating the AST node associated with the function to happen. Will need to look at how to best deal with that integration.