Is Haskell's laziness an elegant alternative to Python's generators?

Question

In a programming exercise, it was first asked to program the factorial function and then calculate the sum: 1! + 2! + 3! +... n! in O(n) multiplications (so we can't use the factorial directly). I am not searching the solution to this specific (trivial) problem, I'm trying to explore Haskell abilities and this problem is a toy I would like to play with.

I thought Python's generators could be a nice solution to this problem. For example :

from itertools import islice
def ifact():
    i , f = 1, 1
    yield 1
    while True:
        f *= i
        i += 1
        yield f

def sum_fact(n):
    return sum(islice(ifact(),5))

Then I've tried to figure out if there was something in Haskell having a similar behavior than this generator and I thought that laziness do all the staff without any additional concept.

For example, we could replace my Python ifact with

fact = scan1 (*) [1..]

And then solve the exercise with the following :

sum n = foldl1 (+) (take n fact)

I wonder if this solution is really "equivalent" to Python's one regarding time complexity and memory usage. I would say that Haskell's solution never store all the list fact since their elements are used only once.

Am I right or totally wrong ?

---

EDIT : I should have check more precisely:

Prelude> foldl1 (+) (take 4 fact)
33
Prelude> :sprint fact
fact = 1 : 2 : 6 : 24 : _

So (my implementation of) Haskell store the result, even if it's no longer used.

Answer 1

Your examples are not equivalent in memory usage. It is easy to see if you replace * with a + (so that the numbers don't get big too quickly) and then run both examples on a big n such as 10^7. Your Haskell version will consume a lot of memory and python will keep it low.

Python generator will not generate a list of values then sum it up. Instead, the sum function will get values one-by-one from the generator and accumulate them. Thus, the memory usage will remain constant.

Haskell will evaluate functions lazily, but in order to calculate say foldl1 (+) (take n fact) it will have to evaluate the complete expression. For large n this will unfold into a huge expression the same way as (foldl (+) 0 [0..n]) does. For more details on evaluation and reduction have a look here: https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27.

You can fix your sum n by using foldl1' instead of foldl1 as described on the link above. As @user2407038 explained in his comment, you'd also need to keep fact local. The following works in GHC with a constant memory use:

let notfact = scanl1 (+) [1..]
let n = 20000000
let res = foldl' (+) 0 (take n notfact)

Note that in case of the actual factorial in place of notfact memory considerations are less of a concern. The numbers will get big quickly, arbitrary-precision arithmetic will slow things down so you won't be able get to big values of n in order to actually see the difference.