Hmm ... but not by much.

| 2. A simple, one-liner using higher order functions has turned into a
|    10 line tail recursive loop.  Now being a Schemer at heart, I have
|    no particular problem with this, but it does seem to go against the
|    whole idea of "higher order functions are good" which most fp books
|    espouse.

I have a couple of comments on this.  Firstly, the problem
is you are getting 000's of thunks.  The problem is *not*
the use of a higher-order function.  Even if you unfolded the
definition of "foldl" at the parameterisation shown, the program would
behave the same.

Secondly, a few minutes of investigation and a few changed lines
made a massive difference to the usability of the program.
In my book this is a very small price to pay for the
convenience of a language as expressive as Haskell.  I believe
a few (say five at most) strategically placed hyperstrictnesses (so to speak)
can make a big difference to the space behaviour of programs
tens of thousands of lines long.  Using a heap-profiling
compiler, it is easy to spot the functions filling the heap up
with thunks.

For this reason, I believe the Haskell committee should
consider the provision of two built-in functions:

   hyperstrict, whnf :: Eq a => a -> b -> b

both of which evaluate their first argument (fully or to whnf)
and return the second.  We can simulate this at the moment using
Haskell 1.2, but it might be more efficient if compilers could
regard these as primitive.

Jules

Consider the following Haskell fragment which reads lines data from a
file into the "store" :-

  read_ASCII_Store st file fail succ = readFile file fail (succ . store)
    where
      store = (foldl (flip process_line) st) . (map words) . lines

where "process_line" has the form :-

  process_line :: [String] -> Store -> Store

This works fine.  It is nice and lazy i.e. if you invoke it, it does
not do anything until you actually try to access some of the values of
"store".  However, there is a price to pay for this.  When the input
file is reasonably large, this creates a large amounts of "thunks"
when reading in the data, in fact the "thunks" dominate the
proceedings and cause much more heap to be used than should be
necessary.  (It runs out of space in a 5Mb for an "interesting" input
file)

This appears to be well known problem (a number of people here have
had similar problems anyway), and the suggested solution is to "force"
the store at regular intervals so that it fully evaluates itself.
This results in the following code, where 100 is the number of lines
to read between "forcing" :-

    store xs = store_loop 0 st (lines xs)
    store_loop n st []    =
      if (st == st)           -- force the store
      then st
      else error "the FORCE is not with us"
    store_loop n st stuff =
      let st' = process_line (words (head stuff)) st
      in if (n `mod` 100 == 0)
         then if (st' == st') -- force the store
              then store_loop (n+1) st' (tail stuff)
              else error "the FORCE was not with us"
         else store_loop (n+1) st' (tail stuff)

This works well, and keeps the usage down to under 2Mb for the input
that previously ran out of heap.  However, there are a couple of
things that bother me about this :-

1. The extra amount of work that has to be done in "forcing" the store.
   This bumps up the runtime.

2. A simple, one-liner using higher order functions has turned into a
   10 line tail recursive loop.  Now being a Schemer at heart, I have
   no particular problem with this, but it does seem to go against the
   whole idea of "higher order functions are good" which most fp books
   espouse.

So, I'm asking the net at large for advice.  Does anybody know of any
other methods of keeping the heap usage low and that do better in
answering 1&2?  Something using continuations or monads maybe?

bevan

* apologies for the imprecise terminology, I hope you all know what I
  mean anyway.

Tony Davie

I've heard from my friends in the ML community that they're thinking about
introducing a new primitive to make it easier to write lazy programs
in ML, much like delay/force in Scheme.

Now I see discussion of introducing a strictness primitive in Haskell.

The two camps are moving closer together.  Indeed, the question begins
to look like a human-factors one: is it more convenient to use a strict
language where the strictness can be turned off on request or a lazy
language that can be made strict in places?
--
                                --Andrew Koenig

   Hmm ... but not by much.

How can we know this?  All I committed myself to was that the runtime
increased.  I can't say by how much, as without forcing the store it
is either slower or doesn't fit in the available heap.  However,
intiution tells me that doing repeated full equality tests on 7 AVL
trees containing 10,000+ elements each cannot be a cheap operation :-)

   | 2. A simple, one-liner using higher order functions has turned into a
   |    10 line tail recursive loop.  Now being a Schemer at heart, I have
   |    no particular problem with this, but it does seem to go against the
   |    whole idea of "higher order functions are good" which most fp books
   |    espouse.

   I have a couple of comments on this.  Firstly, the problem
   is you are getting 000's of thunks.  The problem is *not*
   the use of a higher-order function.

Ah, but I never said it was.  All I pointed out was that a solution to
the problem involved removing the HOF and replacing with an explicit
loop.  If I hadn't have been a HOF in the first place, the solution
whouldn't have seemed such a drastic change.

   Even if you unfolded the definition of "foldl" at the
   parameterisation shown, the program would behave the same.

Actually it runs out of heap quicker than the foldl version.  I guess
foldl isn't being optimised by the compiler.

   ..., I believe the Haskell committee should
   consider the provision of two built-in functions:

      hyperstrict, whnf :: Eq a => a -> b -> b

   both of which evaluate their first argument (fully or to whnf)
   and return the second.  We can simulate this at the moment using
   Haskell 1.2, but it might be more efficient if compilers could
   regard these as primitive.

Doesn't this move us back into the realms of separate annotations.  I
thought many people don't like as there is too much opportunity for
the user to make a mistake i.e. "hyperstricting" everthing in sight in
the hope of efficiency.  Alternately couldn't you argue that as most
of the time you want strict evaluation, you'd be better off with a
language were that was the default and annotating it with "lazy" at
appropriate points? For example, I have a much better feel for where I'd
want a strict version to be lazy than I do about where I'd want a lazy
version to be strict.  Is this the mark of a novice lazy programmer?

That notwithstanding, if the above proposal means I can remove the
loop and replace it with one hyperstrict/whnf call in the
read_ASCII_Store definition, then I'm all for it (but then what do I
know :-)

bevan

        -- Lennart

--

        -- Lennart Augustsson
[This signature is intentionally left blank.]

Sorry about my last posting, the mailer mangled it.

        -- Lennart

--

        -- Lennart Augustsson
[This signature is intentionally left blank.]

Doubtless this article, quoted in its entirety, was generated by an LML
program(mer) that was being too lazy.

---
David Lester, Manchester University, UK.

[ ... but a nice meta-comment anyway, Lennart.]