list - 每个级别(表面级别)LISP 的最大数量

Question

我想从数字列表中计算每个子列表/级别/表面级别的最大值

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 添加到 some-list 的后面。我不知道为什么 nconc acc2 (list head) 不起作用

尝试用 append 替换 nconc，但它也不起作用。显然，您不能使用 append/nconc 将元素添加到空列表。那怎么办呢？

Answer 1

更简单的实现:

(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))))