Упрощение выражений с помощью Racket

Question

У меня есть функция, которая отличает уравнение и выводит его в виде списка на экран. Теперь я хочу создать функцию, которая возвращает выражение, подобное этому: '(+ (* x 0) (* 2 1)) и упрощает ответ. Получает избавление от x * 0, так как это всегда оценивается в ноль и заменяет 2 * 1 на 2, в конечном итоге возвращает только 2, поскольку 2 + 0 равно 2. Это то, что у меня есть до сих пор, и, очевидно, этого очень не хватает, любая помощь в получении это началось с большой благодарностью.

(define (simplify expr) 
    (if (not (list? expr)) 
     expr 
     (if (null? (cdr expr)) 
      (car expr) 
      (case (car expr) 
      ((+ 
       )) 

     )) 

Answer 1

Общее решение для такого рода проблемы не что просто. Для начала, подумайте об использовании правила перезаписи, взгляните на simplify процедуру, показанную в разделе 4 статьи A Hacker's Introduction to Partial Evaluation:

We can use rewrite rules to simplify algebraic expressions. For example, 

> (simplify '(+ (* 3 x) (* x 3))) 
; (* 6 x) 

This works by applying a list of rules to all parts of the subject expression 
repeatedly until no more simplifications are possible: 

(define *simplification-rules* 
    '(((+ ?x ?x)   (* 2 ?x)) 
    ((* ?s ?n)   (* ?n ?s)) 
    ((* ?n (* ?m ?x)) (* (* ?n ?m) ?x)) 
    ((* ?x (* ?n ?y)) (* ?n (* ?x ?y))) 
    ((* (* ?n ?x) ?y) (* ?n (* ?x ?y))))) 

The left hand column has patterns to match, while the right hand holds responses. 
The first rule says, if you see (+ foo foo), rewrite it into (* 2 foo). Variables 
like ?x can match anything, while ?m and ?n can only match numbers. 

Answer 2

Предполагая, что вы просто двоичные выражения с «* и» + как операторы, то достаточно легко закодировать основные правила алгебры с рекурсивным спусками выражения, которое должно быть упрощено. Таким образом:

(define (simplify exp) 
(cond ((number? exp) exp) 
     ((symbol? exp) exp) 
     ((list? exp) 
     (assert (= 3 (length exp))) 
     (let ((operator (list-ref exp 0)) 
       (operand-1 (simplify (list-ref exp 1))) ; recurse 
       (operand-2 (simplify (list-ref exp 2)))) ; recurse 
      (case operator 
      ((+) 
      (cond ((and (number? operand-1) (= 0 operand-1)) operand-2) 
        ((and (number? operand-2) (= 0 operand-2)) operand-1) 
        ((and (number? operand-1) (number? operand-2)) 
        (+ operand-1 operand-2)) 
        (else `(,operator ,operand-1 ,operand-2)))) 

      ((*) 
      (cond ((and (number? operand-1) (= 0 operand-1)) 0) 
        ((and (number? operand-2) (= 0 operand-2)) 0) 
        ((and (number? operand-1) (= 1 operand-1)) operand-2) 
        ((and (number? operand-2) (= 1 operand-2)) operand-1) 
        ((and (number? operand-1) (number? operand-2)) 
        (* operand-1 operand-2)) 
        (else `(,operator ,operand-1 ,operand-2)))) 
      (else 'unknown-operator)))) 
     (else 'unknown-expression))) 

Это только один проход над выражением. Обычно вы хотите выполнять пропуски, пока результат не изменится.