constant space `minimum'

Serge D. Mechveliani mechvel at
Wed Sep 29 01:47:14 EDT 2004

Simon Marlow  responds on the subject of constant space `minimum':

> 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) =3D> [a] -> a
> and we can't assume that the comparison operations for any given type
> are always strict.

I meant that the implementation like

             minimum [x]      = x
             minimum (x:y:xs) = if x > y then minimum (y:xs) 
                                else          minimum (x:xs) 

is correct, and on the other hand, GHC compiles it more readily
into an efficient code than the version done via  foldl  or such.

Serge Mechveliani
mechel at

More information about the Glasgow-haskell-users mailing list