LISP упрощают полиномы

Question

Я пишу программу, которая пока упрощает полиномы, только сложение и умножение.

Я часами стучал головой по клавиатуре и решил, что пришло время обратиться за помощью.

(defun simplify (lis)
    (if (eq (car lis) '+)
        (cons '+ (simplify-addition (cdr lis)))
        (if (eq (car lis) '*)
            (cons '* (simplify-multiplication (cdr lis))) 
        )
    )
)
(defun simplify-addition (lis)
    (if (not (null lis))
        (if (listp (car lis))
            (list (simplify (car lis)) (simplify-addition (cdr lis)))
            (if (numberp (car lis))
                (if (eq (car lis) 0)
                    (simplify-addition (cdr lis))
                    (if (null (cdr lis))
                        lis
                        (cons (car lis) (simplify-addition (cdr lis)))
                    )
                )
                (if (eq (car lis) '+)
                    (list (car lis) (simplify-addition (cdr lis)))
                    (if (eq (car lis) '*)
                        (list (car lis) (simplify-addition (cdr lis)))
                        lis
                    )
                )
            )
        )
    )
)

(defun simplify-multiplication (lis)
    (if (not (null lis))
        (if (listp (car lis))
            (if (find 0 (car lis))
                0
                (list (simplify (car lis)) (simplify-multiplication (cdr lis)))
            )
            (if (numberp (car lis))
                (if (null (cdr lis))
                    lis
                    (cons (car lis) (simplify-multiplication (cdr lis)))
                )
                (if (eq (car lis) '+)
                    (list (car lis) (simplify-multiplication (cdr lis)))
                    (if (eq (car lis) '*)
                        (list (car lis) (simplify-multiplication (cdr lis)))
                        lis
                    )
                )
            )
        )
    )
)

Вот что должно произойти:

(simplify ‘(+  x  ( + 0 3 )  ( * 1 5 )  ( * ( * x  y  z ) 0 )  ))  -->  ( + x 3 5 )
(simplify ‘(* (+ 6  0)  (* 1 6 2)))  -------------------------------->  (* 6 (* 6 2))

но вместо этого я получаю тот же самый многочлен, который я послал, или что-то полностью выключенное

РЕДАКТИРОВАТЬ: Упрощение мне нужно, чтобы удалить 0 из дополнений, так что:

(+ 3 0)   --> 3
(+ 4 0 6) --> (+ 4 6)

и умножение с нуля удаляются

(* 6 0 7) --> 0 

Answer 1

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

• не ставьте скобки в свои строки. Это просто тратит пространство и совсем не помогает.

• не используйте CAR и CDR в доменном коде. Область - математика. Вы используете выражения (operator arg1 arg2), Вместо того, чтобы использовать CAR а также CDR определить функции OPERATOR а также ARGUMENTS и использовать их.

• использование CASE, COND и другие многогранные условные выражения вместо вложенных IF - где полезно.

• попытаться извлечь обход структур данных из кода домена. Используйте функции более высокого порядка вместо рекурсии (MAP, REDUCE...)

Пример:

Некоторые основные доменные функции:

(defun operator (expression)
  (first expression))

(defun arguments (expression)
  (rest expression))

(defun make-expression (operator arguments)
  (if (= (length arguments) 1)
      (first arguments)
    (cons operator arguments)))

(defun is-zero? (expression)
  (and (numberp expression)
       (= expression 0)))

Теперь об упрощениях:

(defun simplify (expression)
  (if (atom expression)
      expression
    (case (operator expression)
      (+ (make-expression '+ (simplify-addition       (arguments expression))))
      (* (make-expression '* (simplify-multiplication (arguments expression)))))))

(defun simplify-addition (expressions)
  (remove-if #'is-zero?
             (mapcar #'simplify
                     (remove-if #'is-zero? expressions))))

(defun simplify-multiplication (expressions)
  (if (member-if #'is-zero? expressions)
      (list 0)
    (let ((expressions1 (mapcar #'simplify expressions)))
      (if (member-if #'is-zero? expressions1)
          (list 0)
        expressions1))))

Видите, насколько читабельнее код? Больше не надо CAR, LIS, CDR, Намерение рекурсивных вызовов также намного яснее для понимания.

Это все еще не оптимально, но это должно помочь вам.

Answer 2

Я только посмотрел на simplify-multiplication но здесь есть ряд вопросов.

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

Во-вторых, я не вижу, чтобы вы проверяли 1 нигде, так что я не вижу, как (* 1 5) ==> 5 должен работать.

В-третьих, давайте пройдем (simplify '(* (+ 2 0) 3)) некоторое время:

(defun simplify-multiplication (lis)
; lis = '((+ 2 0) 3)
    (if (not (null lis))
    ; ==> t
        (if (listp (car lis))
        ; (car lis) = '(+ 2 0), so (listp '(+ 2 0)) ==> t
            (if (find 0 (car lis))
            ; succeeds because '(+ 2 0) contains 0
            ; this is completely wrong! you're not supposed to check sublists of lis
                0
                ; ... yeah, you just returned 0 just because there was a 0 *somewhere*
                (list (simplify (car lis)) (simplify-multiplication (cdr lis)))
            )
            ...

Или же (simplify '(* 0 2)):

(defun simplify-multiplication (lis)
; lis = '(0 2)
    (if (not (null lis))
    ; ==> t
        (if (listp (car lis))
        ; (car lis) = 0, so (listp 0) ==> nil
            (if (find 0 (car lis))
                0
                (list (simplify (car lis)) (simplify-multiplication (cdr lis)))
            )
            (if (numberp (car lis))
            ; (numberp 0) ==> t
                (if (null (cdr lis))
                ; (cdr lis) = '(2), so (null '(2)) ==> nil
                    lis
                    (cons (car lis) (simplify-multiplication (cdr lis)))
                    ; ... wait, what?
                    ; you're just recursively walking through the list without
                    ; checking what numbers you actually got. this won't simplify
                    ; anything.
                )
                (if (eq (car lis) '+)
                ; what is this branch for? it can only succeed if you have code of the form
                ;   (* 1 + 2)
                ; which is a syntax error
                    (list (car lis) (simplify-multiplication (cdr lis)))
                    (if (eq (car lis) '*)
                    ; this branch is for code like (* * *). huh???
                        (list (car lis) (simplify-multiplication (cdr lis)))
                        lis
                    )
                )
            )
        )
    )
)