How to find smallest element in a list

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

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