# Lazy minimum

Dan Doel dan.doel at gmail.com
Thu Nov 20 00:18:34 EST 2008

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