constant space `minimum'
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) =3D> [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, and on the other hand, GHC compiles it more readily into an efficient code than the version done via foldl or such. ----------------- Serge Mechveliani mechel@botik.ru
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.
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@botik.ru
participants (2)
-
Carsten Schultz -
Serge D. Mechveliani