Стандартные Производные Калькулятор Алгебраических


У меня были некоторые трудности с этим проблемы, поэтому я уверен, что есть лучший путь. Вот вопрос из SICP:

Упражнения 2.58

Предположим, что мы хотим модифицировать программу дифференциации так что он работает с обычными математическая запись, в которой + и * является инфиксом, а не префиксные операторы. Поскольку дифференциация программа определяется в терминах абстрактные данные, мы можем изменить его работа с различными представлениями выражения исключительно путем изменения предикатов, селекторы, и конструкторы, которые определяют представление алгебраических выражения, по которым дифференциатор работы.

а. Показать, как это делать для того, чтобы различают алгебраические выражения представленных в инфиксной форме, например

(x + (3 * (x + (y + 2))))

Чтобы упростить задачу, предположим, что + и * всегда принимать два аргумента и что выражения в скобках полностью.

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

(x + 3 * (x + y + 2))

какие капли лишнего скобки и предполагает, что умножение делается раньше дополнение. Можете ли вы разработать соответствующие предикатов, селекторы, и конструкторы для обозначения таких что наши производная программа по-прежнему работает?

Я написал следующее решение части B (некоторые части пришли из текста):

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (join op seq)
  (foldr (lambda (a b) (cons a (if (null? b) b (cons op b)))) null seq))

(define (make-sum . a)
  (define (iter sum rest) 
    (cond ((null? rest) (if (zero? sum) '() (list sum)))
          ((=number? (car rest) 0) (iter sum (cdr rest)))
          ((number? (car rest)) (iter (+ sum (car rest)) (cdr rest)))
          (else (cons (car rest) (iter sum (cdr rest))))))
  (let ((result (iter 0 a)))
    (cond ((null? result) 0)
          ((= (length result) 1) (car result))
          (else (join '+ result)))))

(define (=number? exp num)
  (and (number? exp) (= exp num)))

(define (make-product . a)
  (define (iter product rest)
    (cond ((null? rest) (if (= 1 product) '() (list product)))
          ((=number? (car rest) 1) (iter product 
                                         (cdr rest)))
          ((number? (car rest)) (iter (* product (car rest)) 
                                      (cdr rest)))
          (else 
           (let ((result (iter product (cdr rest))))
             (if (and (pair? result) (eq? (car result) 0))
                 (list 0)
                 (cons (car rest) result))))))
  (let ((result (iter 1 a)))
    (cond ((null? result) 1)
          ((eq? (length result) 1) (car result))
          (else (join '* result)))))

(define (sum? x)
  (and (pair? x) 
       (or 
        (member '+ x)
        (and (eq? 1 (length x)) 
             (pair? (car x)) 
             (pair? (member '+ (car x)))))))

(define (items-before op seq)
  (if (eq? (cadr seq) op)
      (list (car seq))
      (cons (car seq) (items-before op (cdr seq)))))

(define (items-after op seq)
  (if (eq? (car seq) op) 
      (cdr seq)
      (items-after op (cdr seq))))

(define (addend s) (if (and (eq? (length s) 1) (pair? (car s)))
                       (addend (car s))
                       (let ((result (items-before '+ s)))
                         (if (eq? 1 (length result)) (car result) result))))

(define (augend s) (if (and (eq? (length s) 1) (pair? (car s)))
                       (augend (car s))
                       (let ((result (items-after '+ s)))
                         (if (eq? 1 (length result)) (car result) result))))

(define (product? x)
  (define (no-plus-just-times seq) (not (member '+ seq)) (pair? (member '* seq)))
  (and (pair? x) 
       (or 
        (and (no-plus-just-times x))
        (and (eq? (length x) 1) (pair? (car x)) (no-plus-just-times (car x))))))

(define (multiplier p) (if (and (eq? (length p) 1) (pair? (car p)))
                           (multiplier (car p))
                           (car p)))

(define (multiplicand p) (if (eq? (length p) 1) 
                             (if (pair? (car p)) 
                                 (multiplicand (car p)) 
                                 (car p)) 
                             (caddr p)))

Как это может быть улучшено?



623
5
задан 21 апреля 2011 в 01:04 Источник Поделиться
Комментарии