constant space `minimum'

Jerzy Karczmarczuk karczma at
Fri Sep 10 06:29:01 EDT 2004

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

More information about the Glasgow-haskell-users mailing list