How to find smallest element in a list

Provided the list is shorter than about 260,000 elements, you can use apply('min mylist) . Effectively it calls the min function with the list as arguments - and there are some limitations in the stack size used for function arguments, hence the length limit.

Regards,

Andrew.

I have run into the maximum number of elements using the min function. If you think your list could be large, a simple sort will get you the result you want.

minval = car(sort(mylist 'lessp))

Derek

Although using a sort is quite an expensive operation (on a large list) when you only care about the first element of the result. You might be better off doing:

procedure(CCFoverList(func lst)
  let(((result car(lst)))
    foreach(elem lst result=funcall(func result elem))
    result
  )
)

So then you'd use:

CCFoverList('min mylist)

or 

CCFoverList('max mylist)

Regards,

Andrew.

Yes I belive it is, or rather it would be if I'd not made a silly mistake when I typed it in - I meant to do this but accidentally omitted the cdr in the argument to the foreach. So it should be:

procedure(CCFoverList(func lst)
  let(((result car(lst)))
    foreach(elem cdr(lst) result=funcall(func result elem))
    result
  )
)

With the previous min/max examples, you'd not see the difference, but if you use CCFoverList('plus mylist) you'd see it double-counted the first element in the list.

A lispy way of doing it would be to use recursion, but that will also have stack size limitation (maybe if you write it the right way and can use the tail call optimization option, but I didn't spend any time thinking about that - hardly worth it when it is so simple anyway).

Regards,

Andrew.

Andrew Beckett said:

 Provided the list is shorter than about 260,000 elements, you can use apply('min mylist) 

This is a very mysterious business.  Sometimes you can only do 2**16-1:

> toplevel 'ils
> (define bigList nil)
bigList
> (for i 0 2**17 (push i bigList))
t
> (length bigList)
131073
> (apply min bigList)
0
> (apply plus bigList)
*Error* plus: too many arguments (at most 65535 expected, 131073 given)
 - (131072 131071 131070 131069 131068 ... )

How 'come min can handle 131,073 arguments, but not plus? It appears they use diffrent data structures to hold their arguments:

> (for i 2**17+1 2**18 (push i bigList))
t
> (length bigList)
262145
> (apply min bigList)
*Error* min: Value Stack Overflow!!! (possibly due to too many args in a call, 
too deeply nested calls, or too large a function)

So why does plus use what appears to be a fixed-size argument array, while min uses a "Value Stack"? Perhaps their types are a clue?

> getFunType min
lambda
> getFunType plus
primop

Andrew Beckett said:

A lispy way of doing it would be to use recursion, but that will also have stack size limitation (maybe if you write it the right way and can use the tail call optimization option, but I didn't spend any time thinking about that - hardly worth it when it is so simple anyway).

For those who, like me, are curious about the Lispy alternatives Andrew alluded to, here's the definition of accumulate from Abelson and Sussman:

(define (CCFaccumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (CCFaccumulate op initial (cdr sequence)))))

> (CCFaccumulate plus 0 (list 1 2 3 4 5))
15
> (CCFaccumulate times 1 (list 1 2 3 4 5))
120
> (CCFaccumulate cons nil (list 1 2 3 4 5))
(1 2 3 4 5)

As Andrew says, this version will exhaust the stack if given a big list:

> (CCFaccumulate max 0 bigList)
*Error* null?: Runtime Stack Overflow!!!

However, we can transform it into a tail-recursive definition that can handle lists of any size (provided the optimizeTailCall option is on):

(define (CCFtailRecursiveAccumulate op initial sequence)
  (if (null? sequence)
      initial
      (CCFtailRecursiveAccumulate op
                                  (op initial (car sequence))
                                  (cdr sequence))))

> (sstatus optimizeTailCall t)
t
> (for i 2**18+1 2**20 (push i bigList))
t
> (CCFtailRecursiveAccumulate max 0 bigList)
1048577

  --tom

Tom,

The difference is because some functions (e.g. plus, difference, times etc) are "primop" functions which are implemented as virtual machine instructions, and these have a 2^16-1 limit for the arguments. Other functions are "lambda" functions (such as min, max), and these are constrained by the stack they use.

Thanks for showing the tail call optimized version; I didn't have time to put this together when I replied the other day.

Kind Regards,

Andrew.

Before this thread, I did not realize APPLY had a hard limit on the number of arguments!

I recently read a Google Common Lisp Style Guide entry that addresses this very issue:

http://google-styleguide.googlecode.com/svn/trunk/lispguide.xml#REDUCE_vs_APPLY

SKILL doesn't have REDUCE, so I use Andrew's CCFoverList() instead, renamed as "foldl1" due to my time with Haskell.