On Thu, Nov 20, 2008 at 12:18 AM, 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.
Now that I've thought about it more, the problem is that min and max are insufficiently lazy for lists. Here's a list clone that has the desired properties: data List a = Nil | a :< List a deriving (Show, Eq) instance Ord a => Ord (List a) where compare Nil Nil = EQ compare Nil _ = LT compare _ Nil = GT compare (a :< as) (b :< bs) = case compare a b of LT -> LT EQ -> compare as bs GT -> GT min (a :< as) (b :< bs) = case compare a b of LT -> a :< as EQ -> a :< min as bs GT -> b :< bs min _ _ = Nil head' (a :< as) = a head' _ = error "head': empty List" Thus, *Main> head' $ min (2 :< undefined) (2 :< undefined) 2 *Main> minimum [2 :< undefined, 2 :< undefined, 1 :< Nil] 1 :< Nil The tricky part is that derived instances of Ord do not make min (and max) lazy in this way, so you have to write your own. There are also possible space issues, since "min a b" will end up re-creating much of "a" or "b" if they share a large common prefix. <snip>
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. :)
Yeah, my solution falls down there, too.
*Main> minimum [(2 :< undefined) :< Nil, (2 :< undefined) :< Nil, (1
:< Nil) :< Nil]
*** Exception: Prelude.undefined
I don't know if there's a good, general solution here.
--
Dave Menendez