3

我正在尝试编写一个利用代数表达式的分配属性来简化它的过程：

(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)

正如第二个例子所示，可能有不止一种结果，我不需要一一列举，只需要一个有效的结果。我想知道是否有人可以向我提供至少一个关于他们将如何开始攻击这个问题的定性描述？谢谢 ：）

4

2 回答 2

2

Oleg Kiselyov 的pmatch 宏使得跨术语分布因子变得非常容易：

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

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

主要技巧是匹配模式并从模式中相应插槽的表达式中提取元素。这需要一个带有棘手的表达式的condand到列表中的正确位置和正确的元素。写给你。letcdrcarpmatchcondlet

因式分解出公用项更难，因为您必须查看所有子表达式以找到公因式，然后将它们拉出：

(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)))

输出可以再清理一些，这不包括分解出 1，并且 remove-all丢失了，但我会把所有这些都留给你。

于 2013-04-17T08:52:17.040 回答
0

一个非常通用的方法：

(dist expr var-list)
=> expr factored using terms in var-list

dist必须了解“可分发”功能+,-,*,/,etc，以及它们各自的行为方式。如果说，它只知道前四个，那么：

(dist expr var-list
  (if (empty? var-list) expr
    (let* ([new-expr (factor expr (first var-list))])
      (return "(* var " (dist new-expr (rest var-list)))))

"return "(* var " " 语法不正确，但你可能已经知道了。无论如何我都不是球拍或 lisp 专家，但基本上这归结为字符串处理？无论如何，factor需要充实，以便删除单个varfrom*函数和所有varfrom+函数（将它们替换为 1）。它还需要足够聪明，仅在至少有两个替换时才执行此操作（否则我们实际上没有做任何事情）。

于 2013-04-14T08:44:01.840 回答