Finding the minimum element in a list

[I X Code X 1]

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:

Code: Select all

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

[Joe Taylor]

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

Code: Select all

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

[I X Code X 1]

Code: Select all

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

Code: Select all

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

[I X Code X 1]

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:

Code: Select all

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

[crabbe]

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

[ander-skirnir]

Code: Select all

(reduce #'min list)

or

Code: Select all

(apply #'min list)

first is better

[I X Code X 1]

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!

[I X Code X 1]

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.

[Duke]

Your result:

Let me know! lol

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

Code: Select all

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

[Ramarren]

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

Code: Select all

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

Code: Select all

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