Dear GHC developers, The library functions like minimum, maximum, should perform in a constant space: probably, it is easy to write them his way. And ghc-6.2.2-pre shows Prelude> minimum [1 .. (10^4)] 1 Prelude> minimum [1 .. (10^6)] *** Exception: stack overflow Prelude> What do you think of this, please? ----------------- Serge Mechveliani mechvel@botik.ru
"Serge D. Mechveliani"
The library functions like minimum, maximum, should perform in a constant space: probably, it is easy to write them his way.
I haven't given it much thought, but it seems that the rather obvious: Prelude> minimum [1..10^6] *** Exception: stack overflow Prelude> :i minimum -- minimum is a variable minimum :: forall a. (Ord a) => [a] -> a Prelude> let { mini m (x:xs) = if m <= x then mini m xs else mini x xs; mini m [] = m} Prelude> let minimum' (x:xs) = mini x xs Prelude> minimum' [1..10^6] 1 does the trick (unlike the foldr version, which presumably is used by the Prelude). No? -kzm -- If I haven't seen further, it is by standing in the footprints of giants
Serge D. Mechveliani wrote:
The library functions like minimum, maximum, should perform in a constant space: probably, it is easy to write them his way. And ghc-6.2.2-pre shows
Prelude> minimum [1 .. (10^4)] 1
Prelude> minimum [1 .. (10^6)]
*** Exception: stack overflow Prelude>
What do you think of this, please?
Strange, I thought that foldl or foldl1 don't produce such garbage here.
I tested with Hugs, you are right also here, this is not specific to GHC.
minim (x:l) = mi x l where
mi x (y:q) |x
See my next letter -- about compiling of minimum [1 .. (10^6)] with -O. Because, I think, [1 .. (10^6)] is a program which interferes with `minimum', and it depends much on how cleverly this whole expression is complied, for example, `minimum' is in-lined or not. Probably, `minimum' can be rewritten so, that the whole thing will reliably perform in a constant space in the interpreter mode too. And maybe it is, generally, hard to optimize reliably foldl. ----------------- Serge Mechveliani mechel@botik.ru On Fri, Sep 10, 2004 at 12:29:01PM +0200, Jerzy Karczmarczuk wrote:
Serge D. Mechveliani wrote:
The library functions like minimum, maximum, should perform in a constant space: probably, it is easy to write them his way. And ghc-6.2.2-pre shows
Prelude> minimum [1 .. (10^4)] 1
Prelude> minimum [1 .. (10^6)]
*** Exception: stack overflow Prelude>
What do you think of this, please?
Strange, I thought that foldl or foldl1 don't produce such garbage here. I tested with Hugs, you are right also here, this is not specific to GHC.
minim (x:l) = mi x l where mi x (y:q) |x
This one works. But it is brutal, not so exquisite...
Jerzy Karczmarczuk _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
participants (3)
-
Jerzy Karczmarczuk -
Ketil Malde -
Serge D. Mechveliani