# constant space `minimum'

Simon Marlow simonmar at microsoft.com
Tue Sep 28 08:21:05 EDT 2004

In 6.4, minimum & maximum will have specialised versions for Int &
Integer, which will run in constant stack space.  We can't do this in
general, because minimum/maximum have the type

(Ord a) => [a] -> a

and we can't assume that the comparison operations for any given type
are always strict.

Cheers,
Simon

On 10 September 2004 12:17, Serge D. Mechveliani wrote:

> See my next letter -- about compiling of
>                                          minimum [1 .. (10^6)]
> with -O.
> Because, I think,  [1 .. (10^6)]  is a program which interferes with
> `minimum', and it depends much on how cleverly this whole expression
> is complied, for example, `minimum' is in-lined or not.
>
> Probably, `minimum' can be rewritten so, that the whole thing will
> reliably perform in a constant space in the interpreter mode too.
>
> And maybe it is, generally, hard to optimize reliably  foldl.
>
> -----------------
> Serge Mechveliani
> mechel at botik.ru
>
>
>
> On Fri, Sep 10, 2004 at 12:29:01PM +0200, Jerzy Karczmarczuk wrote:
>> Serge D. Mechveliani wrote:
>>
>>> The library functions like  minimum, maximum,
>>> should perform in a constant space: probably, it is easy to write
>>> them his way. And  ghc-6.2.2-pre  shows
>>>
>>>  Prelude> minimum [1 .. (10^4)]
>>>  1
>>>
>>>  Prelude> minimum [1 .. (10^6)]
>>>
>>>  *** Exception: stack overflow
>>>  Prelude>
>>>
>>> What do you think of this, please?
>>>
>>>
>> Strange, I thought that foldl or foldl1 don't produce such garbage
>> here. I tested with Hugs, you are right also here, this is not
>> specific to GHC.
>>
>> minim (x:l) = mi x l where
>>   mi x (y:q) |x<y = mi x q
>>              |otherwise = mi y q
>>   mi x [] = x
>>
>> This one works.  But it is brutal, not so exquisite...
>>
>>
>> Jerzy Karczmarczuk
>> _______________________________________________