constant space `minimum'
Serge D. Mechveliani
mechvel at botik.ru
Fri Sep 10 07:17:23 EDT 2004
See my next letter -- about compiling of
minimum [1 .. (10^6)]
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.
mechel at 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<y = mi x q
> |otherwise = mi y q
> mi x  = x
> This one works. But it is brutal, not so exquisite...
> Jerzy Karczmarczuk
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
More information about the Glasgow-haskell-users