Lazy minimum

[Dan Doel]

On Wednesday 19 November 2008 11:38:07 pm David Menendez wrote:
> One possibility would be to add minimum and maximum to Ord with the
> appropriate default definitions, similar to Monoid's mconcat.

This is probably the most sensible way. However, first seeing this, I wanted to 
see if I could do it with RULES, like so:

    -- this of course fails for Ords where a <= b, b <=a, but a and b are
    -- somehow distinguishable.
    min' :: Ord a => [a] -> [a] -> [a]
    min' as@(a:at) bs@(b:bt)
      | a < b = as
      | b < a = bs
      | otherwise = a : min' at bt -- arbitrary choice here

    minimum' :: Ord a => [[a]] -> [a]
    minimum' = foldl1 min'

    {-# RULES "min-list" min = min' #-}
    {-# RULES "minimum-list" minimum = minimum' #-}

However, trying this gives me complaints about how Ord a cannot be inferred 
from Ord [a], so min and minimum aren't providing the right information for 
min' and minimum'. Perhaps it's unreasonable to expect this to work?

Anyhow, barring that problem, that's probably the best hope one has of 
inserting a fancy procedure for lazy data without reworking the core 
libraries. This also has the issue of not really solving the problem all the 
way down. For instance, I think:

    let a = replicate (2^20) 2
     in minimum [[[a]], [[a]], [[1]]]

still shows bad behavior. So you need an algorithm more clever than the one 
I've come up with. :)

-- Dan