constant space `minimum'

[Serge D. Mechveliani]

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
>