constant space `minimum'

[Carsten Schultz]

Hi!

On Wed, Sep 29, 2004 at 09:47:14AM +0400, Serge D. Mechveliani wrote:
> Simon Marlow  responds on the subject of constant space `minimum':
> 
> 
> > In 6.4, minimum & maximum will have specialised versions for Int &
> > Integer, which will run in constant stack space.  We can't do this in
> > general, because minimum/maximum have the type
> >
> >  (Ord a) => [a] -> a
> >
> > and we can't assume that the comparison operations for any given type
> > are always strict.
> >
> 
> I meant that the implementation like
> 
>              minimum [x]      = x
>              minimum (x:y:xs) = if x > y then minimum (y:xs) 
>                                 else          minimum (x:xs) 
> 
> is correct,

It seems to me that with only minimal assumptions on (>) the above is
actually equivalent to `foldl1 (\ x y -> if x > y then y else x)'.
(And preferable to it.)  But does (\ x y -> if x > y then y else x)
have to be equivalent to min?  What about the following?

data E a b = L a | R b deriving Eq

instance (Ord a, Ord b) => Ord (E a b) where
    compare (L x) (L y) = compare x y
    compare (L _) (R _) = LT
    compare (R _) (L _) = GT
    compare (R x) (R y) = compare x y

    min     (L x) (L y) = L (min x y)
    min     (L x) (R _) = L x
    min     (R _) (L x) = L x
    min     (R x) (R y) = R (min x y)

I think that it is completely reasonable.  Does the report say
anything about this?

Greetings,

Carsten

-- 
Carsten Schultz (2:38, 33:47), FB Mathematik, FU Berlin
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers, 
fingerprint on my home page.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/glasgow-haskell-users/attachments/20040929/cdd74195/attachment.bin