Finding the smallest number in a list in Lisp using only a list in the constructor?

Question

My professor gave us this stumper on the midterm, and unless I'm not looking at it right, it's a pretty tough question that seems simple.

7. Write a lisp function f that finds the minimum value of a list. Assume that the list contains numbers only. For example (f '(3 2 5 4 9 5)) returns 2.

Here's what I have so far:

(defun f (L)
 (cond ((null (cdr L))(car L))    ; <-- I think my break case is wrong, too.
       ((< (car L) (car (cdr L))) (rotatef((car L) (car(cdr L)))))
 (f(cdr L))
 )
)

The compiler is telling me that my use of rotatef is bad.

My logic is to continuously exchange the smallest element with car(cdr L), and always have the car(L) as the smallest element. Then recursively call the cdr until there's only that's the only way I could think to do it. Weird thing though is that he never mentioned rotatef in our notes, so I'm thinking I did something poorly.

Oh great Lisp gods, can you help me? You're my only hope.

Answer 1

Not sure if it's a solution you will like but it's a solution that works:

(defun smallest (list current_small test)
    (cond ((null list) current_small)
          ((funcall test current_small (first list))
            (smallest (rest list) (first list) test))
            (t (smallest (rest list) current_small test))))

(defun check_smallest (current_small current_value)
    (if(> current_small current_value) current_value nil) 
)     
(defparameter mylist (list 3 33 2 1 32 87 -1 -222 45))

(print (smallest (rest mylist) (first mylist) #'check_smallest))

Answer 2

(defun F (L) (apply 'min L) )

Answer 3

This is really an extended comment on Rainer Joswig's beautiful answer.

What his minimum function does is to essentially treat the first element of the list as a running best-guess-at-the-minimum, repeatedly building a new, shorter list with this best guess as its first element. That's really clever, because the whole algorithm for finding the minimum does work like that: guess the first number, compare it with the second and recurse appropriately.

An alternative approach to this sort of problem is to keep this running-best-guess as a distinct argument to the function which is going to compute the minimum. When used like this this alternative argument is sometimes called an 'accumulator' because in other related patterns it's used to accumulate results. This pattern only really works if you are willing to define an auxiliary function to do this work, since you generally don't want the top-level function to have this extra argument.

So, here is Rainer's function rewritten like this:

(defun minimum/tfb (list)
   "function to return the minimum value of a list of numbers, via a recursive helper"
   (when (null list)
     ;; I claim that the empty list is an error, so let's check this
     ;; and say so
     (error "empty lists don't have minima"))
   (labels ((minimum-loop (tail min-so-far)
              ;; TAIL is everything else we need to look at,
              ;; MIN-SO-FAR is the running minimum
              (cond ((null tail)
                     ;; we are done: the running minimum is the minimum
                     min-so-far)
                    ((< min-so-far (first tail))
                     ;; the running minimum is smaller than the first
                     ;; element of TAIL so it is still our best bet:
                     ;; recurse on the rest of TAIL
                     (minimum-loop (rest tail) min-so-far))
                    (t
                     ;; the first element of TAIL is less than or
                     ;; equal to min-so-far, so it is now our best bet
                     (minimum-loop (rest tail) (first tail))))))
     ;; Now start the process (remember we know LIST has at least one
     ;; element, which we use as out best guess).
     (minimum-loop (rest list) (first list))))

It's pretty easy to see that this is just the same as Rainer's function (except it signals an error if the list it's given is empty, which is a matter of opinion), but it uses this local minimum-loop function which does the work and has this extra argument.

It's possible to rewrite this in a slightly more gratuitously-functional way by observing that you can compute the extra argument at the point of call:

(defun minimum/tfb/gratuitous (list)
   "function to return the minimum value of a list of numbers, via a recursive helper"
   (when (null list)
     ;; I claim that the empty list is an error, so let's check this
     ;; and say so
     (error "empty lists don't have minima"))
   (labels ((minimum-loop (tail min-so-far)
              ;; TAIL is everything else we need to look at,
              ;; MIN-SO-FAR is the running minimum
              (if (null tail)
                  ;; we are done: the running minimum is the minimum
                  min-so-far
                ;; We have more to do: recurse, deciding which element
                ;; to use as the running minimum
                (minimum-loop (rest tail)
                              (if (< min-so-far (first tail))
                                  min-so-far (first tail))))))
     ;; Now start the process (remember we know LIST has at least one
     ;; element, which we use as out best guess).
     (minimum-loop (rest list) (first list))))

I don't think this is actually stylistically any better and it might be worse. It's probably what I'd write however. (Python programmers hate my code.)

Finally note that both Rainer's function and my modifications of it are tail recursive. In a language like Scheme these functions would correspond to explicitly iterative processes. Indeed, in Scheme the iteration constructs are defined in terms of tail calls. Scheme also has a nice syntax for this sort of helper function pattern.

Here is a simple transliteration of my second function into a Scheme-family language (Racket):

(define (minimum lyst)
  (when (null? lyst)
    (error "empty lists do not have minima"))
  (define (minimum-loop tail min-so-far)
    (if (null? tail)
        min-so-far
        (minimum-loop (rest tail)
                      (if (< min-so-far (first tail))
                          min-so-far
                          (first tail)))))
  (minimum-loop (rest lyst) (first lyst)))

(Note the annoying spelling of list as lyst because Scheme is a Lisp-1, and note that internal define works like labels in Scheme.)

And here is a conversion of that to use named-let whose purpose is to support this sort of thing:

(define (minimum/loop lyst)
  (when (null? lyst)
    (error "empty lists do not have minima"))
  (let minimum-loop ([tail (rest lyst)]
                     [min-so-far (first lyst)])
    (if (null? tail)
        min-so-far
        (minimum-loop (rest tail)
                      (if (< min-so-far (first tail))
                          min-so-far
                          (first tail))))))

Answer 4

• you should compute a minimum, so let's call the function minimum
• L as a variable name can be replaced by list
• improve indentation and parentheses

Then it looks like this:

(defun minimum (list)
 (cond ((null (cdr list))
        (car list))    ; <-- I think my break case is wrong, too.
       ((< (car list) (car (cdr list)))
        (rotatef ((car list)
                  (car (cdr list)))))
       (minimum
        (cdr list))))

Now you can get rid of CAR, CDR:

(defun minimum (list)
 (cond ((null (rest list))
        (first list))    ; <-- I think my break case is wrong, too.
       ((< (first list) (second list))
        (rotatef ((first list)
                  (second list))))
       (minimum
        (rest list))))

Minimum in the last cond clauses makes no sense, since it expects a list with a boolean:

(defun minimum (list)
 (cond ((null (rest list))
        (first list))    ; <-- I think my break case is wrong, too.
       ((< (first list) (second list))
        (rotatef ((first list)
                  (second list))))
       (t (minimum (rest list)))))

ROTATEF takes how many arguments? ((foo) (bar)) is no useful syntax in Lisp, since you can't put parentheses around a bunch of Lisp forms just so.

(defun minimum (list)
 (cond ((null (rest list))
        (first list))    ; <-- I think my break case is wrong, too.
       ((< (first list) (second list))
        (rotatef (first list)
                 (second list)))
       (t
        (minimum (rest list)))))

What's with an empty list?

(defun minimum (list)
 (cond ((null list)
        nil)
       ((null (rest list))
        (first list))
       ((< (first list) (second list))
        (rotatef (first list)
                 (second list)))
       (t
        (minimum (rest list)))))

ROTATEF makes no sense, since it does not return a minimum.

(defun minimum (list)
 (cond ((null list)
        nil)
       ((null (rest list))
        (first list))
       ((< (first list) (second list))
        (minimum (cons (first list)
                       (rest (rest list)))))
       (t
        (minimum (rest list)))))

Finally add a short documentation string.

(defun minimum (list)
 "recursive function to return the minimum value of a list of numbers"
 (cond ((null list)
        nil)
       ((null (rest list))
        (first list))
       ((< (first list) (second list))
        (minimum (cons (first list)
                       (rest (rest list)))))
       (t
        (minimum (rest list)))))

Explained:

(defun minimum (list)

 "recursive function to return the minimum value of a list of numbers"

 (cond

       ((null list)                      ; list is empty
        nil)

       ((null (rest list))               ; only one element
        (first list))

       ((< (first list) (second list))   ; if first element is smaller than second
        (minimum (cons (first list)      ; call minimum without second element 
                       (rest (rest list)))))

       (t                                ; second is equal or smaller
        (minimum (rest list)))))         ; call minimum without first element

Now we have to test it, too:

CL-USER 24 > (let ((lists '(()
                            (1)
                            (1 2)
                            (2 1)
                            (3 2 1 0)
                            (1 2 3)
                            (3 4 2 1 1)
                            (1 1 12 -1 4 2))))
               (mapcar #'minimum lists))

(NIL 1 1 1 0 1 1 -1)

Answer 5

Go back to the basics.

What's the shortest list your function can receive? The empty list. What should we return for that? It's not clear. Let's just return nil.

What's the next shortest list your function can receive? A list containing a single number. What should return for that? We should return that single number.

Otherwise, we have a list with at least two numbers. There's (car L) (the first number in the list), and there's (cdr L) (all the rest of the numbers in the list). If (car L) is smaller than the smallest number in (cdr L), then we should return (car L). Otherwise, we should return that smallest number from (cdr L).

Now, how can we get the smallest number from (cdr L)? Well, we're already writing the function that does that! We can call (f (cdr L)) to get the smallest number in (cdr L).

(defun f (L)
    (cond
        ; empty list
        ((null (car L)) nil)

        ; list with just one element
        ((null (cdr L)) (car L))

        ; 2 or more elements
        (T (let ((head (car L))
                 (tailMin (f (cdr L))))
                (if (< head tailMin) head tailMin)))))

Answer 6

Parens are meaningful in lisp: this is the problem with your rotatef.

You also need to use funcall: instead of (f ...) write (funcall f ...), this is lisp-1 vs lisp-2 issue.