Distributive Law Simplification

Question

I'm trying to write a procedure that makes use of the distributive property of an algebraic expression to simplify it:

(dist '(+ x y (exp x) (* x 5) y (* y 6)))
=> (+ (* x (+ 1 5))
      (* y (+ 1 1 6))
      (exp x))

(dist '(+ (* x y) x y))
=> (+ (* x (+ y 1))
      y)
; or
=> (+ (* y (+ x 1))
      x)

As the second example shows, there can be more than one possible outcome, I don't need to enumerate them all, just a valid one. I'm wondering if someone could provide me with at least a qualitative description of how they would start attacking this problem? Thanks :)

Answer 1

Oleg Kiselyov's pmatch macro makes distributing a factor across terms pretty easy:

(define dist
  (λ (expr)
    (pmatch expr
      [(* ,factor (+ . ,addends))
        `(+ ,@(map (λ (addend)
                     (list factor addend))
                   addends))]
      [else
        expr])))

(dist '(* 5 (+ x y))) => (+ (5 x) (5 y))

The main trick is to match a pattern and extract elements from the expression from the corresponding slots in the pattern. This requires a cond and let with tricky expressions to cdr to the right place in the list and car out the right element. pmatch writes that cond and let for you.

Factoring out common terms is harder because you have to look at all the subexpressions to find the common factors and then pull them out:

(define factor-out-common-factors
  (λ (expr)
    (pmatch expr
      [(+ . ,terms) (guard (for-all (λ (t) (eq? '* (car t)))
                                    terms))
        (let ([commons (common-factors terms)])
          `(* ,@commons (+ ,@(remove-all commons (map cdr terms)))))]
      [else
        expr])))

(define common-factors
  (λ (exprs)
    (let ([exprs (map cdr exprs)]) ; remove * at start of each expr
      (fold-right (λ (factor acc)
                    (if (for-all (λ (e) (member factor e))
                                 exprs)
                        (cons factor acc)
                        acc))
                  '()
                  (uniq (apply append exprs))))))

(define uniq
  (λ (ls)
    (fold-right (λ (x acc)
                  (if (member x acc)
                      acc
                      (cons x acc)))
                '()
                ls)))


(factor-out-common-factors '(+ (* 2 x) (* 2 y)))
=> (* 2 (+ (x) (y)))

The output could be cleaned up some more, this doesn't cover factoring out a 1, and remove-all is missing, but I'll leave all that to you.