分配律简化

我试图写一个程序，它利用一个代数表达式的分配律的简化它：分配律简化

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

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

来源

2013-04-14 user1641398

我没有采取过的第一个例子解析的时候，但你的第二个例子是“分解出”共同x或y。你是否想要那样做，或者“通过分发”？我知道两者都遵循分配法，但我想这些答案可能会有所不同，具体取决于你在找什么。 – NickO

准确地说，我只是想通过“分解”任何常见因素来表达一个表达式。这也许会是解释它的更好方式。 – user1641398

一个非常普遍的做法：

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

那“回归‘（* VAR’”是不正确的语法，但你可能已经知道，我不是一个球拍或口齿不清。无论如何，基本上这归结为字符串处理？在任何情况下，factor需要充实，以便它从*函数中删除单个var函数和所有var函数从+函数（将它们替换为1）。还需要有足够的聪明，只有做到这一点时，有至少两个置换（否则我们实际上没有做任何事情）。

来源

2013-04-14 08:44:01 NickO

如果你想要做什么，我认为你正在试图做的，你应该使用宏（或可能'apply'），而不是字符串处理。 – Inaimathi

奥列格Kiselyov的pmatch macro使得跨术语分发因素很容易：

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

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

主要的窍门是匹配模式和从该图案中的对应的狭槽提取的表达元件。这需要cond和let棘手的表达式cdr到列表中适当的地点和car出正确的元素。 pmatch经常为你cond和let。

分解出常见术语是很难，因为你必须看所有的子表达式找到共同的因素，然后将它们拉出来：

(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-17 08:52:17

回答

相关问题