small example for space-efficiency via lazy evaluation?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

small example for space-efficiency via lazy evaluation?

Johannes Waldmann-2
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));


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: small example for space-efficiency via lazy evaluation?

Albert Y. C. Lai
On 2018-09-04 12:36 PM, Johannes Waldmann wrote:
>    main = print $ sum $ map (^ 2) $ [ 1 :: Int .. 10^8 ]
[...]
> So, my question is, what do you use as a (teaching) example
> for space-efficiency via lazy evaluation?

I would skip the summing.  Print the whole list.

Sure it would take forever to finish, but during that time I would also
fire up htop or something to show how much memory the process doesn't
use as it progresses.

And change Int to Integer and bump up the upper bound to 10^12 or
something --- or even have no upper bound at all.  And point out how the
printing starts right away as opposed to "waiting for the whole list to
be completely built before printing begins".

And for the sake of engagement, before running the experiment, invite
the students to make predictions about how much memory, how it grows,
how much time before the printing begins, etc.  Learning does not happen
by nodding.  Learn happens by dropping your jaw all the time.

In my class I used these two other examples (because I didn't want to do
I/O yet):

doITerminate = take 2 (foo 0)
   where
     foo n = n : foo (n + 1)

doIEvenMakeSense = take 2 foo
   where
     foo = 0 : foo

They're merely "take 2" because next I also had to showed the detailed
steps of lazy evaluation.  It would be boring to go "take 10".
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.