O'Reilly logo

Real World Haskell by Donald Bruce Stewart, Bryan O'Sullivan, John Goerzen

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Controlling Evaluation

We have a number of options if we want to write our loop to traverse the list only once. For example, we can write the loop as a fold over the list or via explicit recursion on the list structure. Sticking to the high-level approaches, we’ll try a fold first:

-- file: ch25/B.hs
mean :: [Double] -> Double
mean xs = s / fromIntegral n
  where
    (n, s)     = foldl k (0, 0) xs
    k (n, s) x = (n+1, s+x)

Now, instead of taking the sum of the list and retaining the list until we can take its length, we left-fold over the list, accumulating the intermediate sum and length values in a pair (and we must left-fold, since a right-fold would take us to the end of the list and work backwards, which is exactly what we’re trying to avoid).

The body of our loop is the k function, which takes the intermediate loop state and the current element and returns a new state with the length increased by one and the sum increased by the current element. When we run this, however, we get a stack overflow:

$ ghc -O2 --make B.hs -fforce-recomp
$ time ./B 1e6
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.
./B 1e6  0.44s user 0.10s system 96% cpu 0.565 total

We traded wasted heap for wasted stack! In fact, if we increase the stack size to the size of the heap in our previous implementation, using the -K runtime flag, the program runs to completion and has similar allocation figures:

$ ghc -O2 --make B.hs -prof -auto-all -caf-all -fforce-recomp [1 of 1] Compiling Main ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required