Написать функцию в общем lisp, которая будет возвращать отрицание списка

Question

Я получаю эту ошибку с моим текущим кодом:

 LET: illegal variable specification
   (COND (LISTP A (IF (NEGATE A) (NEGATE (REST L)) NIL))
    (T (SETF A (-A) (APPEND (LIST A) (REST L)) (NEGATE (REST L)) NIL)))

мой текущий код:

(defun negate(L)
 (setq x -1)

 (if (not (null L))

  (let ((a (fitst L))
        (cond (listp a
              (if (negate a)
                  (negate (rest L))
                nil))
        (t
         (setf a (-a) (append (list a)(rest L))
               (negate (rest L))
               nil))))
)
))

и тесты, которые необходимо пройти

o List is  (1 2 3 4)  
o Output should be: (-1 -2 -3 -4)

o List is  (1 -2 (3 4))  
o Output should be: (-1 2 (-3 -4) )

Answer 1

В самом вежливом смысле ваш код немного не в порядке.Ты изучаешь Лисп на этой неделе?Это нормально!Это забавный язык, и он действительно может делать удивительные вещи.

Итак, я собираюсь пройтись по созданию рутины и взять вас с собой в тур.

Ваш основной пример -

(defun negate (n) 
  (if (> n 0) (- 0 n)))

(map #'negate '(1 2 3 4))

Ходить по дереву сложнее, но давайте разберемся с идеями.

По сути, у вас есть три варианта ответа: текущий элемент - ноль, список или атом?

(if (not (car seq)) 
  (if (listp (car seq))
    ;;Recurse
    ;;Otherwise negate the current element and append it to the recursed.

Давайте попробуем сначала сделать следующее:

(defun negate-seq (seq)
  (if (not seq)
      (return-from negate-seq))

  (if (listp (car seq))
      (negate-seq seq)
    (list (negate (car seq)) (negate-seq (cdr seq)))))

Отлично!Кроме ...

(negate-seq '(1 2)) ==> (-1 (-2 NIL))

И ...

 (negate-seq '(1 (1 2 -3))) ==> STACK OVERFLOW!

Ох, мальчик.У нас сейчас проблемы.

Во-первых, давайте просто попробуем cons вместо list.Это устраняет странную проблему с вложенными списками.

Очевидно, что мы попали в цикл бесконечной рекурсии.Это не должно быть возможно, потому что у нас охранник not seq.Хорошо, давайте попробуем отладку.Я использую CLISP и могу отследить аргументы с помощью:

(trace 'negate-seq) 

затем,

(negate-seq '(1 (1 2 -3)))

Внезапно я вижу взрыв

1621. Trace: (NEGATE-SEQ '((1 2 -3)))
1622. Trace: (NEGATE-SEQ '((1 2 -3)))
1623. Trace: (NEGATE-SEQ '((1 2 -3)))
1624. Trace: (NEGATE-SEQ '((1 2 -3)))

Crikey,Я забыл свой CDR и составить список дел!Хммммм.

Давайте попробуем это:

(defun negate-seq (seq)
  (if (not seq)
      (return-from negate-seq))

  (if (listp (car seq))
      (cons (negate-seq (car seq))
        (negate-seq (cdr seq)))
    (cons (negate (car seq)) (negate-seq (cdr seq)))))

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

 (negate-seq '(1 (1 2 -3))) =>  (-1 (-1 -2 NIL)

Хммм.Давайте посмотрим на след.

1. Trace: (NEGATE-SEQ '(1 (1 2 -3)))
2. Trace: (NEGATE-SEQ'((1 2 -3)))
3. Трассировка: (NEGATE-SEQ '(1 2 -3))
4. Трассировка: (NEGATE-SEQ' (2 -3))
5. Трассировка: (NEGATE-SEQ '(-3))
6. Трассировка: (NEGATE-SEQ' NIL)
7. Трассировка: NEGATE-SEQ ==> NIL
8. Трассировка: NEGATE-SEQ ==> (NIL)
9. Трассировка: NEGATE-SEQ ==> (-2 NIL)
10. Трассировка: NEGATE-SEQ ==> (-1 -2 NIL)
11. Трассировка: (NEGATE-SEQ 'NIL)
12. Трассировка: NEGATE-SEQ ==> NIL
13. Трассировка: NEGATE-SEQ ==> ((-1 -2 ноль))
14. Трассировка: NEGATE-SEQ ==> (-1 (-1 -2 ноль))

Так что я повторюсь до -3тогда .... это отваливается?Странный.Ах!Я постоянно хватаю CDR вещей.CDR - это всегда список.(cdr '(-3)) - ноль!

Давайте посмотрим здесь ...

(много копается)

Отрицание возвращает ноль при положительном.D'о.

(defun negate (n) 
  (if ( > n 0) 
      (- 0 n)
    n))


(defun negate-seq (seq)
  "Written by Paul Nathan"
  (if (not seq)
      (return-from negate-seq))

  (if (listp (car seq))
      (cons (negate-seq (car seq))
        (negate-seq (cdr seq)))
    (cons (negate (car seq)) 
      (negate-seq (cdr seq)))))

Answer 2

Если вы напишите:

 (defun negate (n)
   (if ( > n 0)
     (- 0 n)
     n))

, тогда вы ограничите свой код действительными числами.

Если вместо этого вы используете примитивную функцию отрицания, предоставленную Common Lisp, она будет работать налюбое число:

(mapcar (function -) '(1 2/3 #C(4 5)))     
--> (-1 -2/3 #C(-4 -5))

Answer 3

Я не уверен, что вы искали мягкое толчок для исправления представленного кода или вы предлагаете другие способы сделать это.Моя первая мысль была о mapcar:

(defun negate-tree (tree)
  (mapcar (lambda (e)
            (cond 
              ((null e) nil)
              ((listp e) (negate-tree e))
              (t (- e))))
          tree))

Затем вы можете обобщить аспект отрицания и написать вместо него map-tree, приняв функцию, применяемую к атомам вдерево:

(defun map-tree (f tree)
  (mapcar (lambda (e)
            (cond 
              ((null e) nil)
              ((listp e) (map-tree f e))
              (t (funcall f e))))
          tree))

Вы можете вызвать его, скажем, с помощью функции унарного отрицания:

(map-tree #'- '(1 -2 (3 4)))

Такой вызов предполагает, что все листья в дереве либо nilподдерживается функцией унарного отрицания.

Принятие nil в качестве возможного листа в дереве делает алгоритм посещения немного грязным, и неясно, должна ли предоставленная функция f применяться ко всем листьям -даже те, которые nil - так что сама функция может решить, следует ли и как обрабатывать nil.

Еще один недостаток этой версии - это то, как она обрабатывает cons-ячейки, которые не собственные списки .Обратите внимание, что функция listp возвращает true для всех cons-ячеек - даже тех, которые не составляют надлежащие списки, - но mapcar требует, чтобы ее входные данные были правильным списком.Мы можем оказаться по нашему пути "listp true", рекурсивно вызывая mapcar, и mapcar не получит неправильный список.Это означает, что алгоритм, приведенный выше, должен был бы проверить cons-ячейки, чтобы увидеть, являются ли они правильными списками, прежде чем передать их mapcar, возможно, обработав те, которые не являются листами (я не хочу здесь говорить «атомы»)или документально подтверждено, что ожидаемая древовидная структура состоит из надлежащих списков правильных списков.

Если вам нужно принять «деревья» верхнего уровня, которые не обязательно сами являются списками, то есть одинокий атом являетсядопустимое дерево, или nil является допустимым деревом, вы можете разорвать составные части функции выше и написать ту, которая использует mapcar только после определения того, что проверяемое дерево является списком.

Answer 4

Этого можно добиться с помощью следующей процедуры:

(defun negate (l)"returns a list of multiplication negative of elements of a list l,
                  element of list l to be each numbers for not to type err,
                  and list l may not be a list of atoms."
  (cond
   ((null l) nil)
   ((consp (car l)) (cons (negate (car l))
                          (negate (cdr l))))
   (t (cons (* -1 (car l))
            (negate (cdr l))))))

Можно также иметь другую версию.Я пытался написать хвосто-рекурсивную процедуру, но она не полностью tr.

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

(defun negate (l)
  (negate-aux l '()))

(defun negate-aux (l A)
  (cond
   ((null l) (reverse A));or A
   ((consp (car l)) (cons (negate (car l))
                          (negate-aux (cdr l) A)))
   (t (negate-aux (cdr l) (cons (* -1 (car l)) A)))))

Answer 5

Вот что я бы сделал.Конечно, я рассматриваю только цифровые списки.Таким образом, он будет выдавать ошибки, если список не весь числовой.