How to print the largest and lowest value in a nes

问题:

I'm trying to develop a simple function that returns the smallest and largest value in Lisp. So far I have the basic solution working for a single Lisp and here is the code

(defun get-smallest-large (lst &optional (smallest 0) (largest 0))
  (setf smallest (first lst))
  (setf largest 0)
  (dolist (nxt lst)
    (if (< nxt smallest)
        (setf smallest nxt)
        (if (> nxt largest)
            (setf largest nxt))))
  (cons smallest largest))

This works like:

(defun get-smallest-large '(1 2 -1 3))
= (-1 . 3)

Now, I can't for the life of me figure out how to change this solution to deal with nested lists so for instance, I entered this:

(defun get-smallest-large '(5 (-2 20 (3)) -6 (-7 13)))
= (-7 . 20)

How would I go about this?

回答1:

Here's one way you can approach it: when you recurse into sublists, process the return values as if they were elements of the outer list also. Example (in Scheme, which is my "native language"; requires SRFI 26):

(define (min-max x (min #f) (max #f))
  (cond ((null? x) (if min (values min max) (values)))
        ((cons? x) (call-with-values (cut min-max (car x) min max)
                                     (cut min-max (cdr x) <...>)))
        (else (values (if (and min (< min x)) min x)
                      (if (and max (> max x)) max x)))))

And here's a direct Common Lisp translation of same, by which I mean that it's not idiomatic CL at all, but presented for CL programmers unfamiliar with Scheme to get an idea of what the Scheme code does. In particular, the Scheme requirement for proper tail recursion still holds, even though CL does not provide that.

(defun min-max (x &optional min max)
  (cond ((null x) (if min (values min max) (values)))
        ((consp x)
         (multiple-value-call #'min-max (cdr x) (min-max (car x) min max)))
        (t (values (if (and min (< min x)) min x)
                   (if (and max (> max x)) max x)))))

回答2:

Your code assumes that all the elements of the list are numbers. But if you have a nested list, then the list can contain lists of numbers, or lists of lists of numbers and so on.

Your list processing loop has to inspect the type of each element and handle that accordingly.

If you see a list, you want to make a recursive call to get-smallest-large to fetch the smallest and largest value from just that list. In the recursive call, you pass those extra two parameters, so that the function will not return a smaller maximum than you have already seen or larger minimum.

Since the return value is a cons, the recursive call might look something like this:

(destructuring-bind (sm . la) (get-smallest-large smallest largest)
  (setf smallest sm largest la))

In Common Lisp, functions can return multiple values; code which returns a pair of numbers as a cons looks like something that was a quick and dirty port of code from a Lisp dialect without multiple value support.

This means that instead of returning (cons smallest largest) (return a single value which is a cell holding two numbers) we can return (values smallest largest) (actually return two values). The recursive call which uses the values then condenses to:

(multiple-value-setq (smallest largest) (get-smallest-large smallest largest))

The two setf calls at the beginning of the function will destroy the correctness of the recursion. If the function is given smallest and largest values on entry, it must honor those values and not simply overwrite them by taking an arbitrary value from the list structure. That code also has another problem in that it assumes that (first lst) is a number. It could be a sublist! And yet another problem: the list could be empty!!!

I suggest doing it like this:

(defun get-smallest-large (list &optional smallest largest)
  ;; 
 )

That is, default smallest and largest to nil, and deal with nil in the rest of the code as indicating "smallest or largest value not known yet". For instance:

 ;; the number we are looking at is smallest so far, if we have not
 ;; seen any number before, or if it is smaller than the smallest one we have
 ;; seen so far.
 (if (or (null smallest) (< nxt smallest))
    (setf smallest nxt))

This will also fix another bug. Think about what your function should return if it is called on an empty list. Surely not (0 . 0): zero does not occur in an empty list. A reasonable representation to return in that case is (nil . nil) which indicates that lowest and highest number are not known.

回答3:

Here's a version that avoids recursion and uses a nice Common Lisp library: iterate:

(ql:quickload :iterate)
(use-package :iterate)

(defun minmax (tree)
  (iter
    (with head := tree)
    (with stack := nil)
    (while (or head stack))
    (cond
      ((and (null head) stack)
       (setf head (cdr (pop stack))))
      ((consp (car head))
       (push head stack)
       (setf head (car head)))
      ((car head)
       (minimize (car head) :into min)
       (maximize (car head) :into max)
       (setf head (cdr head))))
    (finally (return (values min max)))))

This would be a preferred way of doing it for very large, deeply nested trees, it trades some complexity and O(log n) space (used for backtracking) for scalability (other version suggested here would fail to perform on sufficiently large trees, where the limit would be the memory allocated per thread by the Lisp implementation to the stack of this function.)

The benefit of recursive version, however, may be that in principle, it would be easier to make it run several computations in parallel.

---

Using some macro-magic you can then hide the uninteresting bits of the original minmax function (those which only deal with iterating over tree):

(defmacro-clause (FOR var IN-TREE tree)
  "Iterates over TREE in depth-first order"
  (let ((stack (gensym)) (head (gensym)))
    `(progn
       (with ,head := ,tree)
       (with ,stack := ,nil)
       (with ,var := ,nil)
       (while (or ,head ,stack))
       (cond
         ((and (null ,head) ,stack)
          (setf ,head (cdr (pop ,stack)))
          (next-iteration))
         ((consp (car ,head))
          (push ,head ,stack)
          (setf ,head (car ,head))
          (next-iteration)))
       (setf ,var (car ,head) ,head (cdr ,head)))))

(defun minmax (tree)
  (iter
    (for leaf :in-tree tree)
    (minimize leaf :into min)
    (maximize leaf :into max)
    (finally (return (values min max)))))

And have much leaner function, which only shows the important parts.

---

And here's the parallel version of the algorithm using lparallel library:

(ql:quickload :lparallel)
(setf lparallel:*kernel* (lparallel:make-kernel 128))

(lparallel:defpun pminmax (tree &optional min max)
  (labels ((%min (&rest numbers)
             (iter (for i :in numbers) (when (numberp i) (minimize i))))
           (%max (&rest numbers)
             (iter (for i :in numbers) (when (numberp i) (maximize i)))))
    (cond
      ((null tree) (cons min max))
      ((consp (car tree))
       (lparallel:plet
           ((head (pminmax (car tree) min max))
            (tail (pminmax (cdr tree) min max)))
         (cons (%min (car head) (car tail) min)
               (%max (cdr head) (cdr tail) max))))
      (t (destructuring-bind (new-min . new-max)
             (pminmax (cdr tree) min max)
           (cons (%min (car tree) new-min min)
                 (%max (car tree) new-max max)))))))

Unfortunately, lparallel doesn't yet implement an alternative for multiple-value-bind, so we had to combine the results into a cons cell, but given some persistence it would be possible to implement the parallel version of the above macro and get rid of this unfortunate limitation (which is left as an exercise for the reader).

回答4:

Use the well known function flatten to flatten first your nested list, before you apply your own minimax function on it.

(defun flatten (x)
  (cond ((null x) nil)
        ((atom x) (list x))
        (t (append (flatten (car x))
                   (flatten (cdr x))))))

Then apply:

(get-smallest-large (flatten '(5 (-2 20 (3)) -6 (-7 13))))
;; returns: (-7 . 20)

It works, because

(flatten '(5 (-2 20 (3)) -6 (-7 13)))
;; returns: (5 -2 20 3 -6 -7 13)

Since the list is flat, you can apply your original function on it.

Using flatten, you can write a universal get-smallest-large* function, which works both with nested and flat lists:

(defun get-smallest-large* (lst &optional (smallest 0) (largest 0))
  (get-smallest-large (flatten lst) smallest largest))

;; now you call on any lists - flat or nested:
(get-smallest-large* '(5 (-2 20 (3)) -6 (-7 13)))

If the list is huge, you have to think of generator lists and generator flatten. This is explained here https://www.cs.northwestern.edu/academics/courses/325/readings/list-gen.php