Lazy minimum

[David Menendez]

On Thu, Nov 20, 2008 at 12:18 AM, Dan Doel <dan.doel at gmail.com> wrote:
> 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 <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>