Безкрайно мързелив факториел в 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