constant space `minimum'

[Simon Marlow]

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
>> _______________________________________________
>> Glasgow-haskell-users mailing list
>> Glasgow-haskell-users at haskell.org
>> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>> 
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users