Как исправить мою функцию упрощения для степенного правила (чтобы облегчить чтение результатов) для работающей функции символьного дифференцирования в Racket?

Question

Это моя функция для дифференциации, которая работает правильно.

#lang racket

(define (diff x expr) 
  (if (not (list? expr))
      (if (equal? x expr) 1 0) 
  (let ( (operation (car expr)) 
         (u (cadr expr))
         (v (caddr expr)))
       (case operation
          ((+) (list '+ (diff x u) (diff x v))) 
          ((-) (list '- (diff x u) (diff x v))) 
          ((*) (list '+                             
                     (list '* u (diff x v))
                     (list '* v (diff x u))))       
          ((/) (list '/ (list '- (list '* v (diff x u)) (list '* u (diff x v))) 
                     (list '* v v)))                
          ((^) (list '* v (list '* (list '^ u (- v 1)) (diff x u ))))                           
))))

, и теперь у меня также работает большая часть функции упрощения, которая работает правильно, но где-то есть проблема, и я думаю, что это в моем упрощенном правиле

(define(simplify expr)
  (if (not (list? expr)) expr
  (let ((operation (car expr))      
       (a (simplify (cadr expr)))   
       (b (simplify (caddr expr)))) 
   (case operation 
        ((+) (if (and (number? a)(= a 0)) b    
                 (if (number? b) (if (= b 0) a 
                                     (+ a b)) 
                 (list operation a b)))) 

        ((-) (if (and (number? a) (= a 0)) (- b)         
                 (if (number? b) (if (= b 0) a  
                                     (- a b))
                 (list operation a b)))) 

        ((*) (cond [(number? a)
                    (cond [(= 1 a) b]
                          [(= 0 a) 0]
                          [else (if (number? b)
                                    (cond [(= b 1) a]
                                          [(= b 0) 0]
                                          [else (* a b)])
                                    (list operation a b))])]
                   [(and (number? b) (= b 0)) 0]
                   [(list operation a b)]))
;The case a/b where b=1 is currently only simplified if a is number. Insert an extra case into the cond expression handling b=1
        ((/) (cond [(number? a)
                    (cond [(= 1 b) a]
                          [(= 0 a) 0]
                          [else (if (number? b)
                                    (cond [(= b 1) a]
                                          [(= b 0) 0]
                                          [else (/ a b)])
                                    (list operation a b))])]
                   [(and (number? b) (= b 0)) 0]; this is where an error should be thrown
                         (cond [(= b 1) 1]
                   [(list operation a b)]))

       ((^) (cond [(number? a)
                   ;if a is 1, 1^x is always 1
                   (cond [(= a 1) 1]
                         [else (if (number? b)
                                   ;if a and b are 0 throw error else anything ^0 is 1.
                                   (cond [(= b 0) (if (= a 0) (error "A and B are both 0, statement undefined!") 1)]
                                         ;if b is 1, x^1 is always x
                                         [(= b 1) a]
                                         ;else a^b
                                         [(expt a b)])
                                   ;a or b are continuations
                                   (list operation a b))])]                                  
                   [else (list operation a b)]))
 ))))

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

(simplify '(/ x 1)) ;why is this not working correctly
(simplify '(+ (* (^ x 5) 0) (* 3 (* 5 (* (^ x 4) 1)))) ;not simplifying correctly
(simplify '(* 3 (* (^ x 2) 1))) ;not simplifying correctly
;(simplify '(/ 1 0));not working 
;(simplify '(^ 0 0));this works fine just returns an exception

Answer 1

Сокращенное решение

Используя встроенную способность Racket для вычисления числа (и выполнения правильных сообщений об ошибках, например деление на ноль ошибок)

#lang racket

(define (simplify expr)
  (if (not (list? expr)) 
      expr
      (cond ((= 1 (length expr)) (simplify (car expr)))
            ((= 2 (length expr))
             (let ((operation (car expr))
                   (a (simplify (cadr expr))))
               (case operation
                 ((-) (cond ((number? a) (- a))
                            (else (list operation (simplify a)))))
                 ((+) (cond ((number? a) a)
                            (else (simplify a))))
                 (else (error "Diadic operator with only one argument given.")))))
            ((= 3 (length expr))        
             (let ((operation (car expr))        
                   (a (simplify (cadr expr)))     
                   (b (simplify (caddr expr))))   
               (case operation  
                 ((+) (cond ((and (number? a) (number? b)) (+ a b)) 
                            ((number? a) 
                             (cond ((zero? a) (simplify b)) 
                                   (else (list operation (simplify a) (simplify b))))) 
                            ((number? b) 
                             (cond ((zero? b) (simplify a))
                                   (else (list operation (simplify a) (simplify b)))))
                            (else (list operation (simplify a) (simplify b)))))
                 ((-) (cond ((and (number? a) (number? b)) (- a b)) ;; use Racket's ability to subtract
                            ((number? a)
                             (cond ((zero? a) (- (simplify b)))
                                   (else (list operation (simplify a) (simplify b)))))
                            ((number? b)
                             (cond ((zero? b) (simplify a))
                                   (else (list operation (simplify a) (simplify b)))))
                            (else (list operation (simplify a) (simplify b)))))
                 ((*) (cond ((and (number? a) (number? b)) (* a b)) ;; use Racket's ability to mulitpy
                            ((number? a)
                             (cond ((zero? a) 0)
                                   ((= a 1) (simplify b))
                                   (else (list operation (simplify a) (simplify b)))))
                            ((number? b)
                             (cond ((zero? b) 0)
                                   ((= b 1) (simplify a))
                                   (else (list operation (simplify a)(simplify b)))))
                            (else (list operation (simplify a) (simplify b)))))
                 ((/) (cond ((and (number? a) (number? b)) (/ a b)) ;; use Racket's ability to divide
                            ((number? a)
                             (cond ((zero? a) 0)
                                   (else (list operation (simplify a) (simplify b)))))
                            ((number? b)
                             (cond ((zero? b) (error "Divison by 0, statement undefined!"))
                                   ((= b 1) (simplify a))
                                   (else (list operation (simplify a) (simplify b)))))
                            (else
                             (list operation (simplify a) (simplify b)))))
                 ((^) (cond ((and (number? a) (number? b)) (expt a b)) ;; use Racket's ability to exponentiate
                            ((number? a)
                             (cond ((= a 1) 1)  ;; ((zero? a) 0) ;; depends on b [b < 0 then undefined]
                                   (else (list operation (simplify a) (simplify b)))))
                            ((number? b)
                             (cond ((zero? b) 1) ;; depends on a [a = 0 then undefined]
                                   ((= b 1) (simplify a))
                                   (else (list operation (simplify a) (simplify b)))))
                            (else (list operation (simplify a) (simplify b)))))))))))

Для некоторых примеров, которые заканчиваются только числами и операторами, это помогает применить simplify несколько раз.Например, (simplify (simplify (simplify '(+ (+ (* 2 1) (* x 0)) 0)))) возвращает 2.

Объяснение более короткого решения

Вначале выражение if проверяет, является ли выражение списком или нет(not (list? expr)).Если нет, это означает, что выражение является либо числом, либо символом переменной.Поэтому мы их возвращаем (expr).В противном случае мы знаем, что expr составлен - список - в форме (<operator - one of */-+^> <first-operand - called a here> <second-operand 'b'>).Мы проверяем длину списков с помощью предложений cond.Если длина равна 1 (= 1 (length expr)), это означает, что были установлены некоторые лишние скобки, например ((+ 1 2)) или (1), поэтому мы возвращаем (car expr), чтобы выражение избавилось от лишних паратезов.Если длина списка равна 2, то мы можем обработать такие случаи, как (+ 3) => 3 или такой лишний знак плюс.или более сложные выражения (+ (* 3 4)).Так что во всех случаях мы рекурсивно вызываем simplify для результатов.

Если выражение имеет длину 3, мы анализируем операцию, первый операнд a и второй операнд b.Тогда, по словам оператора, у нас есть разные правила упрощения, которым нужно следовать.Однако в инструкциях используется один и тот же шаблон.

;; each of the case branches has the pattern:
((<operator>) (cond ((and (number? a) (number? b)) (<operator> a b))
                    ((number? a)
                    ...)
                    ((number? b)
                    ...)
                    (else
                      (list operation (simplify a) (simplify b)))))

Первое предложение с условием (and (number? a) (number? b)) охватывает случай, когда оба операнда являются числами.Этот случай прост для обработки, потому что Racket уже «знает», как обрабатывать основные математические операции.Таким образом, вы просто вычисляете значение и возвращаете его как упрощение (таким образом: (<operator> a b) как возвращаемое значение).Примечание. В случае /, если b равно нулю, возникает ошибка Division by zero.Но Racket поднимает его автоматически, если мы даем ноль для b,, поэтому здесь мы просто позволяем Racket также поднять ошибку и просто возвращаем и вычисляем Racket (/ a b).

Вторым пунктом является случай, когда a это число.Поскольку первый тест должен был провалиться, теперь мы точно знаем , что хотя бы один из a или b, если не оба, составлены из форм или символов, а не чисел.Если это условие верно, мы знаем, что a - это число, но b должно быть составлено.(Если бы b было бы числом, первое условие дало бы истину ...).Как инструкция, у нас снова есть cond с предложениями.Пункты обрабатывают особые случаи a как число.Сложение + и Вычитание - оба являются инвариантами 0, поэтому первая проверка для обеих ветвей здесь заключается в том, равно ли a нулю (zero? a).В этом случае мы опускаем оператор и a=0 и возвращаем только b.Но поскольку b, безусловно, является составной формой, мы вызываем simplify для нее, чтобы рекурсивно упростить b (в противном случае выражение b было бы задано как есть без дальнейшего упрощения).Если a не равен нулю, мы приходим к предложению else, зная, что a является ненулевым числом и b должно быть составной формой.Таким образом, мы перечислили операторы и a и b, каждый из которых упрощен.На самом деле a не нуждается в дальнейшем упрощении, поскольку мы знаем, что это число.Вы можете удалить simplify вызов около a и просто написать a.Для * и / мы различаем 3 случая:

• , если a равно нулю для * или /, то мы знаем, что все становится равным нулю, поэтому мы возвращаемся к этомуукажите 0 для всего выражения.
• затем мы запрашиваем инвариант для * или /, что составляет 1.Таким образом (= 1 a) Итак, мы возвращаем в этом случае (simplify b) без a и оператора.

В третьем предложении, в случае, когда b является числом и составлено a, все то же самое, что и в предыдущем предложении - просто заменяя везде b на a.И только одно исключение: для /, если b равно нулю, то должна быть выдана ошибка division by zero.Таким образом, мы поднимаем здесь ошибку на (error "Divison by 0, statement undefined!").Поскольку a не является числом, мы не можем позволить Racket вычислить здесь что-либо, поэтому мы вручную поднимаем ошибку.

Четвертое предложение (else) будет вызываться, только если a и b, сами составлены, так как все предыдущие тесты по этому пути не прошли.В этом случае мы рекурсивно вызываем (simplify a) и (simplify b) и перечисляем эти результаты вместе с оператором в виде списка.Таким образом, для каждого операнда будет применяться описанный здесь процесс упрощения.

Важное замечание: Привязки let для a и b также вызывают simplify для операндов.Если мы пропустим здесь вызовы simplify, упрощение прекращается после одного уровня.Таким образом, и вызовы simplify - те, что в привязках let - и те, что находятся в конце cond - ветвей ниже по потоку - необходимы для "протягивания" рекурсии вниз по всему дереву выражений - как мы видели накануневчера, когда я забыл simplify в предложениях cond;).Таким образом, эти два уровня вызовов simplify действуют как двигатели, которые тянут процесс упрощения до самого дна ...

Решение

(define (simplify expr)
  (if (not (list? expr))
      expr
      (let ((operation (car expr))
            (a (cadr expr))
            (b (caddr expr)))
        (case operation
          ((+) (cond ((and (number? a) (number? b))
                      (cond ((zero? a) b)
                            ((zero? b) a)
                            (else (+ a b))))
                     (else (list operation (simplify a) (simplify b)))))
          ((-) (cond ((and (number? a) (number? b))
                      (cond ((zero? a) (- b))
                            ((zero? b) a)
                            (else (- a b))))
                     (else (list operation (simplify a) (simplify b)))))
          ((*) (cond ((and (number? a) (number? b))
                      (cond ((or (zero? a) (zero? b)) 0)
                            ((= a 1) b)
                            ((= b 1) a)
                            (else (* a b))))
                     ((number? a)
                      (cond ((zero? a) 0)
                            ((= a 1) (simplify b))
                            (else (list operation (simplify a) (simplify b)))))
                     ((number? b)
                      (cond ((zero? b) 0)
                            ((= b 1) (simplify a))
                            (else (list operation (simplify a)(simplify b)))))
                     (else (list operation (simplify a) (simplify b)))))
          ((/) (cond ((and (number? a) (number? b))
                      (cond ((zero? b) (error "Divison by 0, statement undefined!"))
                            ((zero? a) 0)
                            ((= b 1) a)
                            (else (/ a b))))
                     ((number? a)
                      (cond ((zero? a) 0)
                            (else (list operation (simplify a) (simplify b)))))
                     ((number? b)
                      (cond ((zero? b) (error "Divison by 0, statement undefined!"))
                            ((= b 1) (simplify a))
                            (else (list operation (simplify a) (simplify b)))))
                     (else
                      (list operation (simplify a) (simplify b)))))
          ((^) (cond ((and (number? a) (number? b))
                      (cond ((and (zero? a) (zero? b)) (error "A and B are both 0, statement undefined!"))
                            ((zero? a) (if (< b 0)
                                           (error "Exponent undefined for 0 and negative B.")
                                           0))
                            ((zero? b) 1)
                            ((= a 1) 1)
                            ((= b 1) a)
                            (else (expt a b))))
                     ((number? a)
                      (cond ((zero? a) 0) ;; depends on b actually - if b < 0 then undefined
                            ((= a 1) 1)
                            (else (list operation (simplify a) (simplify b)))))
                     ((number? b)
                      (cond ((zero? b) 1) ;; depends on a actually - if a = 0 then undefined
                            ((= b 1) (simplify a))
                            (else (list operation (simplify a) (simplify b)))))
                     (else (list operation (simplify a) (simplify b)))))))))

Старая версия

(define (simplify expr)
  (if (not (list? expr))
      expr
      (let ((operation (car expr))
            (a (simplify (cadr expr)))
            (b (simplify (caddr expr))))
        (case operation
          ((+) (cond ((and (number? a) (= a 0)) b)
                     ((and (number? b) (= b 0)) a)
                     ((and (number? b) (number? a)) (+ a b))
                     (else (list operation (simplify a) (simplify b)))))
          ((-) (cond ((and (number? a) (= a 0)) (- b))
                     ((and (number? b) (= b 0)) a)     
                     ((and (number? a) (number? b)) (- a b))
                     (else (list operation (simplify a) (simplify b)))))
          ((*) (cond ((and (number? a) (= a 1)) b)
                     ((and (number? a) (= a 0)) 0)
                     ((and (number? a) (number? b) (= b 1)) a)
                     ((and (number? a) (number? b) (= b 0)) 0)
                     ((and (number? a) (number? b)) (* a b))
                     ((and (number? b) (= b 1)) a)               ;; added by me
                     ((and (number? b) (= b 0)) 0)
                     (else (list operation (simplify a) (simplify b)))))
          ((/) (cond ((and (number? a) (= a 0)) 0)
                     ((and (number? a) (number? b) (= b 1)) a)
                     ((and (number? a) (number? b) (= b 0)) (error "Divison by 0, statement undefined!")) ;; error added
                     ((and (number? a) (number? b)) (/ a b))
                     ((and (number? b) (= b 1)) a)               ;; added by me
                     ((and (number? b) (= b 0)) (error "Divison by 0, statement undefined!")) ;; error added
                     (else (list operation (simplify a) (simplify b)))))
          ((^) (cond ((and (number? a) (= a 1)) 1)
                     ((and (number? a) (number? b) (= a 0) (= b 0)) (error "A and B are both 0, statement undefined!"))
                     ((and (number? a) (number? b) (= b 0)) 1)
                     ((and (number? a) (number? b) (= b 1)) a)
                     ((and (number? a) (number? b)) (expt a b))
                     ((and (number? b) (= b 1)) a)               ;; added by me
                     ((and (number? b) (= b 0)) 1)               ;; corrected to 1 (before: zero)
                     (else (list operation (simplify a) (simplify b)))))))))

Это упрощает правильно.Я написал это довольно неэффективно (с последующим cond), поэтому - я «упросту» ответ: D.Я добавил комментарий, какие строки я добавил.Это упрощает (simplify '(+ (* (^ x 5) 0) (* 3 (* 5 (* (^ x 4) 1))))) до '(* 3 (* 5 (^ x 4))), что лучше (трюк состоит в том, чтобы рекурсивно вызывать simplify для каждого из операндов в предложениях else. Однако я хотел бы иметь (* 15 (^ x 4)) в конце.Для этого нам нужно еще несколько проверок ...