CODEWITHSUNDEEP
haskelllazy-evaluationfactorial
elm
elm

Reputation: 20435

Infinitely lazy factorial in Haskell

In a similar fashion as the Fibonacci series may be generated as follows,

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

how to define the series for factorial.

Update

Embarrassingly enough, tried this quite before adding this question,

Prelude> let factorial = 2 : 6 : zipWith(*) factorial (tail factorial)
Prelude> take 5 factorial
[2,6,12,72,864]

Indeed the numbers in the tail are not successive values, to start with.

Upvotes: 3

Views: 4636

Answers (4)

Hani
Hani

Reputation: 381

factorials = helper [1..]

helper (x:xs) = x : help ([x * (head xs)] ++ (tail xs))

Upvotes: 0

Zeta
Zeta

Reputation: 105985

Lets take a step back and remember where that lazy version actually comes from:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

We can also define the factorial similarly:

factorial 0 = 1
factorial n = factorial (n - 1) * n

As you can see, our zipping operation is actually (*), and the second list won't be a sublist of factorials, but instead [x..] with an appropriate x:

factorials = 1 : zipWith (*) factorials [x..]

What value should x be? Well, the second element should be 1 = 1 * 1, so it's 1, naturally:

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

Note that we only need to give the first element, since we don't use tail or something similar. As you can see, your attempt was almost correct. You just used the wrong values for the left hand side:

Prelude> let factorial = 2 : 6 : zipWith (*) [4..] (tail factorial)
Prelude> take 10 $ factorial
[2,6,24,120,720,5040,40320,362880,3628800,39916800]

Remark: The factorial sequence is 0!, 1!, 2!, ..., so if you want to be OEIS compliant start with [1,1,...].

Upvotes: 9

Reid Barton
Reid Barton

Reputation: 15029

The idiomatic definition of a lazy list of factorials is not recursive at all: instead it uses the Prelude function scanl.

factorials = scanl (*) 1 [1..]

Upvotes: 7

Shoe
Shoe

Reputation: 76298

Given the usual definition of factorial:

factorial :: Integer -> Integer 
factorial 0 = 1
factorial i = foldr (*) 1 [2..i]

we can generate an infinite list of all factorials by simply running the factorial function over an infinite list of all positive numbers:

inFact :: [Integer]
inFact = map factorial [0..]

Live demo

Upvotes: 3

Related Questions