[Haskell-cafe] Re: Tutorial uploaded

[Cale Gibbard]

On 21/12/05, Tomasz Zielonka <tomasz.zielonka at gmail.com> wrote:
> On Wed, Dec 21, 2005 at 07:13:07PM +0000, Philippa Cowderoy wrote:
> > > Try running
> > >
> > >     putStrLn (unlines (repeat "hello!"))
> > >
> > > You may be surprised ;-)
> >
> > Or not ;-) But yes, I should've checked and my comments on how that'll
> > behave stand. It would be nice to think something clever could happen
> > regarding memory management as well, but I'm familiar enough with GCed
> > systems by now to be somewhat wary of cleverness.
>
> I don't know how it's done, but when you compile it with 'ghc -O2',
> the program runs in constant space. Unfortunately with Hugs and GHCi it
> grows.
>
It really shouldn't grow at all, and at least in my short tests in
ghci and hugs, it doesn't grow for me. The putStrLn won't force any
more of the string than it wants to print at any moment, and
afterward, that part of the string is garbage, and should get
collected right away.

There are two ways to make a Haskell program more efficient: Make it
stricter, or make it lazier.

What do I mean by the latter? Simply that if you can design each part
of your program (as much as possible) to be able to output something
only given a small prefix of its input, then you'll often see some
really nice efficiency. The pipeline scheduler which I wrote for a
summer job made heavy use of this fact, and at a few points in the
design/coding, I made ridiculously large performance gains in both
memory consumption and runtime simply by making sure that lists and
other structures were lazily produced. In the end, the result was a
(combinatorially large) list of all the possible schedules for the
given input code, in order of algorithm greediness. Taking the head of
the list was essentially running the greedy algorithm, but if the
greedy solution, say, couldn't be register allocated, the next item in
the list could be observed, which would backtrack a bit and find
another. In fact, the entire algorithm was designed this way. That's
essentially what the list monad gives you, after all.

Leaning on laziness can result in very elegant generative algorithms
which run quite quickly. Strictness is really only desired when you
are trying to collapse something large down into a small summary.
That's what things like foldl' are for.

 - Cale