constant space `minimum'
Serge D. Mechveliani
mechvel at botik.ru
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.
mechel at botik.ru
More information about the Glasgow-haskell-users