constant space `minimum'
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.
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)]
>>> Prelude> minimum [1 .. (10^6)]
>>> *** Exception: stack overflow
>>> 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
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
More information about the Glasgow-haskell-users