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

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

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

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

Обновить

Как ни смущает, попробовал это еще до того, как добавить этот вопрос,

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

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


lazy-evaluation haskell factorial
person elm    schedule 22.10.2014    source источник
comment
Что вы пробовали? SO не занимается решением задач, но мы можем подтолкнуть вас в правильном направлении, если вы приложите усилия.   -  person chi    schedule 22.10.2014
comment
factorials = <gap> : <gap> : zipWith (*) <gap> (tail factorials). Заполнить пробелы.   -  person Zeta    schedule 22.10.2014
comment
@chi, полностью согласен; обратите внимание на обновление с безрезультатной (смущающей) попыткой еще до формулировки этого вопроса   -  person elm    schedule 22.10.2014
comment
Предыдущая попытка аналогична ряду Фибоначчи, только с умножением список соответствует 2^fib(i+1)*3^fib(i).   -  person Petr    schedule 22.10.2014

Ответы (3)


arrow_upward
9
arrow_downward

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

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

person Zeta    schedule 22.10.2014
comment
Факторная последовательность, определенная в A000142 OEIS, начинается с [1, 1, 2, ...], а не [2, ...]. Просто говорю. - person Shoe; 22.10.2014

arrow_upward
6
arrow_downward

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

factorials = scanl (*) 1 [1..]
person Reid Barton    schedule 22.10.2014
comment
В Haskell 1.2 можно было написать даже products [1..] :-) - person yatima2975; 22.10.2014

arrow_upward
3
arrow_downward

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

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

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

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

Демо

person Shoe    schedule 22.10.2014
comment
Большое спасибо за идеи :) - person elm; 22.10.2014