Finding the minimum element in a list

Hello,

Here's a basic looping question and what I thought was going to be a trivial problem. I want to find the smallest number in a list. The function min does not take a list, so I tried loop through it:

(defun select (a)
  (let ((x 0))
    (loop for i from 1 to (length a) do
          (if (< i x)
              (print (setf x i))))))

Could someone please point me in the right direction? This is definitely not returning what I want it to. Is there a simple way to find the smallest element in a list? If not, how might I alter my program to get the expected results?

This is what I am getting:

CG-USER(42): (SELECT '(1 2 3))
NIL

Thanks in advance!

The simplest option is probably to apply the list of numbers as arguments to min.

(apply #'min '(6 85 34 9 2 98))

(defparameter *y* 0)
(defun select (a)
  (let ((x 10))
    (loop for i from 1 to (length a) do
          (if (< (nth *y* a) x)
              (setf x (nth *y* a))
            (setf x x))
          (setf *y* (1+ *y*)))
    x))

Okay, so I was able to find the minimum of a list this way. But it's quite verbose and sloppy. I'd also like to avoid using global variables if at all possible. Is there anyway to do this within a let? It seems that I cannot update y if it's inside the let. It stays at 0 the entire time. Also, for now just assume the numbers are all under 10 (x 10).

Any tips on cleaning this function up?


EDIT:

Okay, I was being a bit dumb here. I can easily do it without a global variable using let. Just need to use setf

Though, I still would like to make it a bit more clean, and I have my first number being 10. How can I make it so the first number in the list is assigned to x no matter what? Setting x to nil to begin was my first idea, but you cannot say is 1 < nil. Any ideas? Here's what I got:

(defun select (a)
  (let ((x 10)
        (y 0))
    (loop for i from 1 to (length a) do
          (if (< (nth y a) x)
              (setf x (nth y a))
            (setf x x))
          (setf y (1+ y)))
    x))

Cleaned it up again

It now does everything I want it to do: it doesn't have to have a predefined "high-number" and it returns the correct results every time. Only thing I want to know now is, any better ways to do this? To reiterate, I am finding the smallest number in a list. As far as I know there is no built-in function that works with lists. min does not take a list.

My result:

(defun select (a)
  (let ((x (first a))
        (y 1))
    (loop for i from 2 to (length a) do
          (if (< (nth y a) x)
              (setf x (nth y a))
            (setf x x))
          (setf y (1+ y)))
    x))

Your result:

Let me know! lol


Thanks!

Is there a reason you don't want to use apply?

* (defun select (l)
(apply #'min l))
SELECT
* (SELECT '(1 2 3))
1
* (select '(3 1 2))
1

-r

(reduce #'min list)

or

(apply #'min list)

first is better

Haha well that's a bit less complex than what I did. Well, at least I got some more experience playing around with some of the lisp language.

Thanks for the help!

crabbe wrote:Is there a reason you don't want to use apply?

* (defun select (l)
(apply #'min l))
SELECT
* (SELECT '(1 2 3))
1
* (select '(3 1 2))
1

-r

To answer this question: I did consider using apply but for some reason (which I can't remember now) something was not working. Probably was just me being tired at the moment. As for reduce, I completely forgot about it. Really shouldn't have slipped from my mind so easily.

I X Code X 1 wrote: Your result:

Let me know! lol

Here's my solution and a little test I did:

(defun generate-list (n)
  (labels ((rec (lst n)
             (if (> n 0)
                 (rec (cons (random 10000) lst) (1- n))
                 lst)))
    (rec nil n)))

(defun my-min (lst)
  (labels ((rec (lst min)
             (cond ((null lst) min)
                   ((< (car lst) min) (rec (cdr lst) (car lst)))
                   (t (rec (cdr lst) min)))))
    (rec lst (car lst))))

I do like me some tail recursion...

For n=1000

CL-USER> (time (my-min sample-list))
43,008 processor cycles

CL-USER> (time (apply #'min sample-list))
53,184 processor cycles

n=10000

CL-USER> (time (my-min sample-list))
459,144 processor cycles

CL-USER> (time (apply #'min sample-list))
810,024 processor cycles

n=100000

CL-USER> (time (my-min sample-list))
3,511,728 processor cycles

CL-USER> (time (apply #'min sample-list))
36,217,608 processor cycles


The exact numbers vary drastically between runs, but APPLY is clearly slower, and also runs out of stack frames when n = 1000000, so there's nothing wrong with rolling your own solution when you need to. You might refer to your Lisp implementation's own MIN function and see what it does differently to your attempt.

Using REDUCE is obviously best, but some notes about LOOP (although I personally prefer iterate, same principles apply).

LOOP has a number of finders/collectors, and you should check if what you want to do can be done with them. Looking at LOOP CLHS page and searching for "mini" or something like that would reveal

(let ((list '(5 4 2 3 6 1))) (loop for x in list minimizing x))

Also in most cases you shouldn't bind variables outside the loop and modify anything with SETF. When using LOOP it is best to use it as a self contained construct. LOOP has also sequence iterators. If you are using NTH on a list in a loop then something is definitely wrong. Using LOOP a minimization function could be defined as:

(defun select (list)
  (loop for l in (cdr list)
        for x = (first list) then (min x l)
        finally (return x)))

Not really in a loop, but I guess it can be put inside it

(defun min-list (mlist)
   (eval `(min ,@mlist)))

Indecipherable wrote:Not really in a loop, but I guess it can be put inside it

(defun min-list (mlist)
   (eval `(min ,@mlist)))

No. Just, no!

Indecipherable wrote:Not really in a loop, but I guess it can be put inside it

(defun min-list (mlist)
   (eval `(min ,@mlist)))

As a rule of thumb, don't use eval unless what you are doing really needs an evaluator (e.g. if you are generating functions on-the-fly or if you need an interpreter of some sort).

Why not? It's perfectly legal and correct code. Using

(defun min-list (mlist)
   (apply #'min mlist))

would be more efficient, though.

It's slow, ugly and unnecessary. Also, Lispers who view your code will think you couldn't find a better way to deal with the problem because, in general, using eval when not needed is very common among newbies.

It would be more efficient to use reduce instead of apply (it has already been said in this thread) because, in general, it is faster to call functions with only two arguments then with many arguments. Not to mention that there is a limit on the number of arguments a function can take, so reduce would work more generally.

EVAL is something like the UUOC of the lisp world...