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

Indeed, lazy lists can be used this way. There are some subtle differences though:

• Lists are data structures. So you can keep them after evaluating them, which can be both good and bad (you can avoid recomputation of values and to recursive tricks as @ChrisDrost described, at the cost of keeping memory unreleased).
• Lists are pure. In generators you can have computations with side effects, you can't do that with lists (which is often desirable).
• Since Haskell is a lazy language, laziness is everywhere and if you just convert a program from an imperative language to Haskell, the memory requirements can change considerably (as @RomanL describes in his answer).

But Haskell offers more advanced tools to accomplish the generator/consumer pattern. Currently there are three libraries that focus on this problem: pipes, conduit and iteratees. My favorite is conduit, it's easy to use and the complexity of its types is kept low.

They have several advantages, in particular that you can create complex pipelines and you can base them on a chosen monad, which allows you to say what side effects are allowed in a pipeline.

Using conduit, your example could be expressed as follows:

import Data.Functor.Identity import Data.Conduit import qualified Data.Conduit.List as C  ifactC :: (Num a, Monad m) => Producer m a ifactC = loop 1 1   where     loop r n = let r' = r * n                 in yield r' >> loop r' (n + 1)  sumC :: (Num a, Monad m) => Consumer a m a sumC = C.fold (+) 0  main :: IO () main = (print . runIdentity) (ifactC $= C.isolate 5 $$ sumC) -- alternatively running the pipeline in IO monad directly: -- main = (ifactC $= C.isolate 5 $$ sumC) >>= print 

Here we create a Producer (a conduit that consumes no input) that yields factorials indefinitely. Then we compose it with isolate, which ensures that no more than a given number of values are propagated through it, and then we compose it with a Consumer that just sums values and returns the result.