25

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.

5
  • 3
    There are some similarities, but also some differences: Python generators do not give you access to previously visited elements, unless you explicitly store them in some other object.
    – isekaijin
    Nov 16, 2014 at 0:23
  • 1
    The closest analog to Python-style generators (C#: IEnumerator, Rust: Iterator, etc.) I can think of is the notion of Producers, in Gabriel Gonzalez' excellent pipes library.
    – isekaijin
    Nov 16, 2014 at 0:26
  • I would say that they're a more of a generalization of them in some ways, but Python's generators also can act as coroutines, which are rather nice in very specific circumstances.
    – bheklilr
    Nov 16, 2014 at 0:58
  • 3
    "So (my implementation of) Haskell store the result, even if it's no longer used." The result is only stored because 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. Nov 16, 2014 at 2:05
  • also, if you compile the file with -O2, the individual numbers won't be stored, because the only top-level entity that matters is main. They are stored in the interpreter, because you're using the interpreter. :)
    – Will Ness
    Nov 16, 2014 at 19:39

3 Answers 3

15

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.

1
  • Judging from the first paragraph of the pipes tutorial: if you don't need effects in your generator, using simple lists is fine, as long as you understand strictness. Correct? (Your answer seems to confirm this, but then you talk about libraries, and it's unclear if they have any advantage over lists in the specific case described in the original question...)
    – Nickolay
    May 1, 2018 at 19:09
13

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.

3
  • Thanks for you answer. What I understand of @user2407038 comment to the question, if I write fold1 (+) (take n fact) where fact = scan1 (*) [1..], then there won't be memory consumption. Right or not?
    – Sebastien
    Nov 16, 2014 at 12:41
  • 1
    @Sebastien: See my update. You have to use foldl1' instead of foldl1. Have a look at the page I linked to.
    – Roman L
    Nov 16, 2014 at 13:52
  • one thing to note is that Haskell's optimizer will notice this very effectively and will give the same performance as the foldl' version most of the time.
    – semicolon
    Jun 27, 2017 at 21:17
8

Basically, yes: Haskell's lazy-lists are a lot like Python's generators, if those generators were effortlessly cloneable, cacheable, and composeable. Instead of raising StopIteration you return [] from your recursive function, which can thread state into the generator.

They do some cooler stuff due to self-recursion. For example, your factorial generator is more idiomatically generated like:

facts = 1 : zipWith (*) facts [1..]

or the Fibonaccis as:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

In general any iterative loop can be converted to a recursive algorithm by promoting the loop-state to arguments of a function and then calling it recursively to get the next loop cycle. Generators are just like that, but we prepend some elements each iteration of the recursive function, `go ____ = (stuff) : go ____.

The perfect equivalent is therefore:

ifact :: [Integer]
ifact = go 1 1
  where go f i = f : go (f * i) (i + 1)

sum_fact n = sum (take n ifact)

In terms of what's fastest, the absolute fastest in Haskell will probably be the "for loop":

sum_fact n = go 1 1 1
  where go acc fact i
          | i <= n = go (acc + fact) (fact * i) (i + 1)
          | otherwise = acc

The fact that this is "tail-recursive" (a call of go does not pipe any sub-calls to go to another function like (+) or (*)) means that the compiler can package it into a really tight loop, and that's why I'm comparing it with "for loops" even though that's not really a native idea to Haskell.

The above sum_fact n = sum (take n ifact) is a little slower than this but faster than sum (take n facts) where facts is defined with zipWith. The speed differences are not very large and I think mostly just come down to memory allocations that don't get used again.

3
  • Small nitpick: you'll probably need to add some bang patterns to have GHC produce a tight loop. Nov 16, 2014 at 15:18
  • 1
    @AlpMestanogullari In my trials (replacing * with + and evaluating for n = 10^8 multiple times) changing to a form with explicit seq calls to remove the thunks actually had less (positive) impact than the (negative) impact of writing the guards in reverse order with a >; at neither time was it really substantial.
    – CR Drost
    Nov 16, 2014 at 15:51
  • @AlpMestanogullari You really underestimate GHC, GHC will pretty darn reliably pick up on such optimizations, I'm sure you can come up with a pathological case given enough time, but usually code like this will do just fine.
    – semicolon
    Jun 27, 2017 at 21:19

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.