Максимальное количество на каждом уровне (поверхностный уровень) LISP

Я хочу рассчитать максимум каждого подсписка/уровня/поверхностного уровня из списка номеров

Ex: (1 2 5 (4 2 7 (4 6) 9) 7 8) => (8 9 6)

Что у меня есть сейчас:

maximum (l) ;;function to compute the maximum number for a simple list, it works

(defun max-superficial (lista acc acc2) ;;main function: lista - my list, acc - my final list 
                                        ;;of results, acc2 - accumulation list for a sublist 
    (typecase lista 
        (null 
            (typecase acc2

;; if my list is empty and I have nothing accumulated, just return the final list
                (null acc)

;;if my list is empty but I have something in my accumulation list, just add the maximum 
;;of acc2 to my final list
                (t (nconc acc (list (maximum acc2))))))

        (cons (destructuring-bind (head . tail) lista
            (typecase head
                (list

;;if my list isn't empty and the head of the list is a list itself, call 
;;the function again for the head with an empty accumulation list and then call it again 
;;for the tail
                            (nconc acc 
                                (list (max-superficial head acc nil))
                                (max-superficial tail acc acc2)))

;; otherwise just accumulate the head and call the function for the tail 
---problem here             (t (nconc acc2 (list head))
                             (print '(wtf))
                             (print acc)
                             (print acc2)
                             (print head)
                             (max-superficial tail acc acc2)))))))

Проблема в том, что я только написал эту программу и хочу ее протестировать и в списке "---проблема здесь" она не добавляет мою голову в список накопления.

For: (max-superficial '(1 2) nil nil) --result should be ==> wtf nil (1) 1 wtf nil (1 2) 2 2
                                                   My result: wtf nil nil 1 wtf nil nil 2 nil

Я проверил отдельно, и (nconc some-list (list 3)) делает именно то, что должен... добавляет число 3 в конец списка. Я не знаю, почему nconc acc2 (list head) не работает

Пробовал заменить nconc на append, тоже не работает. По-видимому, вы не можете добавить элемент в пустой список, используя append/nconc. Тогда как?


list max lisp common-lisp clisp
person Mocktheduck    schedule 28.11.2015    source источник
comment
Я сейчас на мобильном телефоне и не могу подробно прочитать весь ваш код, но обратите внимание, что nconc деструктивен: он изменяет последний cdr во всех своих аргументах, кроме последнего. Вы также используете некоторые цитируемые списки. Это может привести к неожиданным результатам.   -  person Joshua Taylor    schedule 29.11.2015
comment
См., например, stackoverflow.com/questions/18790192/   -  person Joshua Taylor    schedule 29.11.2015
comment
замена nconc на append решает вашу проблему?   -  person sds    schedule 29.11.2015
comment
Нет, не решает. Тем не менее, он не будет накапливать мои элементы   -  person Mocktheduck    schedule 29.11.2015
comment
Я не знаю, как этот вопрос помогает мне. Мой nconc просто ничего не делает и не добавляет   -  person Mocktheduck    schedule 29.11.2015

Ответы (2)


arrow_upward
1
arrow_downward

Более простая реализация:

(defun max-superficial/sublists (list)
  (loop for num in list
       if (listp num) append (max-superficial/sublists num) into sublists
       else if (numberp num) maximize num into max
       else do (error "Not a number or list: ~a" num)
       finally (return (cons max sublists))))

;; If you want the max of each "level" or depth in a tree,
;; then you need to be able to operate on levels. Here are some
;; functions that are analogous to FIRST, REST, and POP:

(defun top-level (tree)
  (remove-if-not #'numberp tree))

(defun rest-levels (tree)
  (apply #'append (remove-if-not #'listp tree)))

(defmacro pop-level (tree)
  `(let ((top (top-level ,tree)))
     (setf ,tree (rest-levels ,tree))
     top))

(defun max-superficial (tree &key use-sublists)
  "It wasn't clear if you wanted the max in each sublist or the max
at each depth, so both are implemented. Use the :use-sublists key
to get the max in each sublist, otherwise the max at each depth
will be computed."
  (if use-sublists
      (max-superficial/sublists tree)
      (loop for top-level = (pop-level tree)
         collect (if top-level (reduce #'max top-level)) into result
         unless tree do (return result))))
person Throw Away Account    schedule 29.11.2015
comment
Предполагается ли, что это возвращает (1 2 3) как для '(1 (2 (3))), так и для '(1 (2) (3))? (Это не совсем понятно из ОП...) - person gsg; 29.11.2015
comment
Он упомянул как подсписки, так и уровни. Я обновил код для работы с уровнями или подсписками в зависимости от аргумента &key. - person Throw Away Account; 29.11.2015
comment
Выглядит здорово, но я должен использовать только основные операции lisp, поэтому не работаю с деревьями. @gsg (1 2 3) Это правильный ответ. Я привел пример там, вы можете ясно видеть, что я имею в виду. - person Mocktheduck; 29.11.2015

arrow_upward
0
arrow_downward

Вот (не особенно эффективное) решение:

(defun max-avoiding-nil (a b)
  (cond ((null a) b)
    ((null b) a)
    (t (max a b))))

(defun depth-maximum (a b)
  (cond ((null a) b)
    ((null b) a)
    (t
     (cons (max-avoiding-nil (car a) (car b))
           (depth-maximum (cdr a) (cdr b))))))

(defun tree-max-list (list depth)
  (reduce #'depth-maximum tree
          :key (lambda (elt) (tree-max elt depth))
          :initial-value '()))

(defun tree-max (tree depth)
  (if (listp tree)
      (tree-max-list tree (1+ depth))
    (append (make-list depth 'nil) (list tree))))

(defun tree-maximums (tree)
  (tree-max-list tree 0))

(tree-maximums '(1 2 5 (4 2 7 (4 6) 9) 7 8)) => (8 9 6)
(tree-maximums '()) => nil
(tree-maximums '(1)) => (1)
(tree-maximums '((2))) => (nil 2)
(tree-maximums '((2) (3))) => (nil 3)
person gsg    schedule 29.11.2015
comment
Я не должен использовать такие функции, как сокращение или #, :, лямбда. Я новичок, и я хочу решить это самым простым способом, используя только списки. - person Mocktheduck; 29.11.2015