[Haskell-cafe] small example for space-efficiency via lazy evaluation?

Johannes Waldmann johannes.waldmann at htwk-leipzig.de
Tue Sep 4 16:36:01 UTC 2018

Dear Cafe,

I wanted to demonstrate that

  main = print $ sum $ map (^ 2) $ [ 1 :: Int .. 10^8 ]

without any optimisations, still runs in constant space
because garbage is collected immediately.

Except that it does not:

  ghc -O0 space.hs -rtsopts -ddump-simpl
  ./space +RTS -M80k -A10k

gives me unoptimized Core as expected, but exhausts the heap.

After some experimentation, I found that replacing
Prelude.sum   with   Data.Foldable.foldl' (+) 0
achieves what I want. I think the reason is that
instance Foldable [] implements  sum  by  foldl  (non-strict).

Both versions will run without any allocation
as soon as we compile with  -O1 .

So, my question is, what do you use as a (teaching) example
for space-efficiency via lazy evaluation?

Preferrably a one-liner, using only standard libraries,
and such that the effect is not rendered moot by  -O2.

- J

PS: It is magic that  foldl  and  foldl'  produce identical core here?

          $wgo_s5we (w_s5w8 :: GHC.Prim.Int#) (ww1_s5wc :: GHC.Prim.Int#)
            = case GHC.Prim.==# w_s5w8 ww_s5w5 of {
                __DEFAULT ->
                  jump $wgo_s5we
                    (GHC.Prim.+# w_s5w8 1#)
                    (GHC.Prim.+# ww1_s5wc (GHC.Prim.*# w_s5w8 w_s5w8));

More information about the Haskell-Cafe mailing list