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.
Indeed, lazy lists can be used this way. There are some subtle differences though:
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With