constant space `minimum'

Ketil Malde ketil+haskell at
Fri Sep 10 05:46:33 EDT 2004

"Serge D. Mechveliani" <mechvel at> writes:

> The library functions like minimum, maximum, should perform in a
> constant space: probably, it is easy to write them his way.

I haven't given it much thought, but it seems that the rather obvious:

    Prelude> minimum [1..10^6]
    *** Exception: stack overflow
    Prelude> :i minimum
    -- minimum is a variable
    minimum :: forall a. (Ord a) => [a] -> a
    Prelude> let { mini m (x:xs) = if m <= x then mini m xs else mini x
    xs; mini m [] = m}
    Prelude> let minimum' (x:xs) = mini x xs
    Prelude> minimum' [1..10^6]

does the trick (unlike the foldr version, which presumably is used by
the Prelude).  No?

If I haven't seen further, it is by standing in the footprints of giants

More information about the Glasgow-haskell-users mailing list