Рекурсивная обработка элементов списка в LISP

Question

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

(1 2 NIL (2 4 6) 5 7) -> (1 2 NIL 12 5 7) 

, если родительский список соответствует условию после преобразования:

(2 2 (4 4) (2 2)) -> (2 2 8 4) -> 16

Теперь у меня есть следующий код:

;; check  for all list elements are even 
(defun is-even-list (lst)
    (cond ((null lst) t)
        ((and (numberp (car lst)) (evenp (car lst))) (is-even-list (cdr lst)))      
        (t nil)
    )
)

;; list summing 
(defun sum-list (lst)
    (cond ((null lst) 0)
        (t (+ (car lst) (sum-list (cdr lst))))
    )
) 

;; main func 
(defun task (lst)
    (cond ((null lst) nil)
        ((atom (car lst)) (cons (car lst) (task (cdr lst))))
        ((is-even-list (car lst)) (cons (list (sum-list (car lst))) (task (cdr lst))))
        (t (cons (task (car lst)) (task (cdr lst))))
    )
)

Но сейчасон обрабатывает только «самый низкий» уровень списка, если он существует:

(2 4)               -> (2 4)
(2 (2 4 6) 6)       -> (2 12 6)
(2 (4 (6 8) 10) 12) -> (2 (4 14 10) 12)
(2 (4 6) (8 10) 12) -> (2 10 18 12)

Как я могу изменить этот код, чтобы получить «полную» обработку?

Answer 1

Позвольте мне показать некоторые улучшения в вашем собственном ответе.

Во-первых, используйте обычное форматирование: нет висячих скобок, тела с отступом в два пробела, другие формы аргументов выровнены.Используйте соответствующие разрывы строк.

(defun is-even-list (lst)
  (cond ((null lst) t)
        ((and (numberp (car lst))
              (evenp (car lst)))
         (is-even-list (cdr lst)))            
        (t nil)))

(defun sum-list (lst)
  (cond ((null lst) 0)
        (t (+ (car lst)
              (sum-list (cdr lst))))))

(defun test (lst)
  (dotimes (i (list-length lst))
    (cond ((not (atom (nth i lst)))
           (setf (nth i lst) (test (nth i lst))))))
  (cond ((is-even-list lst) (setf lst (sum-list lst)))
        ((not (is-even-list lst)) (setf lst lst))))

Первая функция проверяет две вещи: каждый элемент является числом и каждый элемент является четным.В этом контексте первое условие в основном означает: нет подсписков.

(defun flat-all-even-p (list)
  (and (every #'numberp list)
       (every #'even list)))

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

(defun sum (list)
  (reduce #'+ list))

Третья функция не проверяет , она сумм .Обратите внимание, что он только случайно возвращает ответ, так как setf возвращает значение, которое он устанавливает.Другая проблема заключается в том, что вы делаете поиск по спискам в цикле, что очень неэффективно.Наконец, вы изменяете список, который вам дали, что удивит вашего абонента.

(defun sum-if-all-even (tree)
  (if (listp tree)
      (let ((recursed-tree (mapcar #'sum-if-all-even tree)))
        (if (flat-all-even-p recursed-tree)
            (sum recursed-tree)
            recursed-tree))
      tree)

Answer 2

Вот решение, которое, я думаю, отвечает требованиям вопроса: рекурсивно суммируйте список, каждый элемент которого является четным числом или список, удовлетворяющий одному и тому же требованию.Это также делает это, делая только один проход по структуре, которую он пытается суммировать.Для больших списков в реализации он полагается на устранение хвостовых вызовов, что, вероятно, всегда верно, но не обязательно.sum-list-loop может быть превращено во что-то явно итеративное, если нет.

(defun sum-list-if-even (l)
  ;; Sum a list if all its elements are either even numbers or lists
  ;; for which this function returns an even number.  If that's not
  ;; true return the list.  This assumes that the list is proper and
  ;; elements are numbers or lists which meet the same requirement but
  ;; it does not check this in cases where it gives up for other
  ;; reasons first: (sum-list-if-even '(2 "")) signals a type error
  ;; (but (sum-list-if-even '(1 "")) fails to do so)
  (labels ((sum-list-loop (tail sum)
             (etypecase tail
               (null sum)               ;all the elements of '() are even numbers
               (cons
                (let ((first (first tail)))
                  (etypecase first
                    (integer
                     ;; Easy case: an integer is either an even number
                     ;; or we give up immediately
                     (if (evenp first)
                         (sum-list-loop (rest tail) (+ sum first))
                       ;; give up immediately
                       l))
                    (list
                     ;; rerurse on the car ...
                     (let ((try (sum-list-if-even first)))
                       ;; ... and check to see what we got to know if
                       ;; we should recurse on the cdr
                       (if (not (eq try first))
                           (sum-list-loop (rest tail) (+ sum try))
                         l)))))))))
    (sum-list-loop l 0)))

Answer 3

Это определенно не лучшее решение, но оно работает:

(defun is-even-list (lst)
    (cond ((null lst) t)
        ((and (numberp (car lst)) (evenp (car lst))) (is-even-list (cdr lst)))      
        (t nil)
    )
)

(defun sum-list (lst)
    (cond ((null lst) 0)
        (t (+ (car lst) (sum-list (cdr lst))))
    )
) 

(defun test (lst)   
    (dotimes (i (list-length lst))      
        (cond           
            ((not (atom (nth i lst))) (setf (nth i lst) (test (nth i lst))))
        )
    )

    (cond       
        ((is-even-list lst) (setf lst (sum-list lst)))
        ((not (is-even-list lst)) (setf lst lst))       
    )   
)