Бесконечно ленивый факториала в Haskell

Question

Подобным же образом, как ряд Фибоначчи могут быть получены следующим образом,

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

как определить ряд для факториала.

Update

достаточно Смущающе, попытался это довольно, прежде чем добавить этот вопрос,

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

Действительно числа в хвосте не последовательные значения, чтобы начать с.

Answer 1

Давайте сделаем шаг назад и вспомним, откуда эта ленивая версия:

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

Мы можем также определить факториал аналогично:

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

Как вы можете видеть, наша проносясь операция на самом деле (*), а второй список не будет подсписка factorials, но вместо этого [x..] с соответствующим x:

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

Какое значение должно x быть? Ну, второй элемент должен быть 1 = 1 * 1, так что 1, естественно:

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

Обратите внимание, что нам нужно только сделать первый элемент, так как мы не используем tail или что-то подобное. Как вы можете видеть, ваша попытка была почти правильной. Вы просто использовали неправильные значения для левой стороны:

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

Примечание: Факториал последовательность 0 !, 1 !, 2 !, ..., поэтому, если вы хотите, чтобы быть совместимым с начала OEIS [1,1,...].

Answer 2

Учитывая обычное определение factorial:

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

мы можем генерировать бесконечный список всех факториалов, просто запустив функцию factorial над бесконечным списком всех положительных чисел:

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

Live demo

Answer 3

Идиоматическое определение ленивого списка факториалов вообще не рекурсивно: вместо этого оно использует функцию Prelude scanl.

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