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.
IEnumerator
, Rust:Iterator
, etc.) I can think of is the notion ofProducer
s, in Gabriel Gonzalez' excellent pipes library.fact
is a top level value and can be accessed by anyone, anywhere. If you define it in a let binding and consume its elements 1 by 1, old elements would be garbage collected as soon as they were consumed.main
. They are stored in the interpreter, because you're using the interpreter. :)