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 1e6Stack 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 ...