constant space `minimum'

[Serge D. Mechveliani]

On Wed, Sep 29, 2004 at 01:50:28PM +0200, Carsten Schultz wrote:
> 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
> 

I do not know. Probably, the Haskell Library Report should specify 
something close to what  minimum  means mathematically, and the
remaining details may remain flexible. The precise language semantics
is too complex.

-----------------
Serge Mechveliani
mechvel at botik.ru