haskelllazy-evaluationfactorial

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.


Solution

  • 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,...].