Создать бесконечный список с числами Фибоначчи

foldr (со строгой функцией объединения) разбирает список аргументов до самого конца, а затем повторно объединяет его с помощью предоставленной пользователем функции объединения f:

foldr f z [a,b,c,...,y] = f a (f b (f c (.....(f y z).....)))

в твоем случае,

fibs2 = reverse $ foldr (\_ (x:y:xs) -> (x+y):x:y:xs) [1,0] [0..]

foldr здесь никогда не производит никакого вывода. Но это не из-за отсутствия попыток: он очень усердно рекурсирует по бесконечному списку в поисках его конца, потому что его функция объединения строгая (она сопоставляет остальную часть вывода foldr с (x:y:xs) перед построением своего собственный результат).

Foldr со строгой функцией объединения выражает рекурсию, а рекурсия должна иметь свой базовый случай, чтобы остановиться. Вы имели в виду следующее:

fibs2 = reverse $ snd $ until (null.fst) 
         (\(_t:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])

который явно не прекращается. ts просто выражает проходящие моменты времени. Мы можем попытаться увидеть всю историю ее исполнения, переписав ее как

fibs2 = reverse $ snd $ last $ iterate
         (\(_t:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])

Конечно, в бесконечном списке нет последнего элемента. Но мы можем хотя бы увидеть все промежуточные результаты уже сейчас:

> mapM_ (print.reverse.snd) $ take 11 $ iterate 
          (\(_:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])
[0,1]
[0,1,1]
[0,1,1,2]
[0,1,1,2,3]
[0,1,1,2,3,5]
[0,1,1,2,3,5,8]
[0,1,1,2,3,5,8,13]
[0,1,1,2,3,5,8,13,21]
[0,1,1,2,3,5,8,13,21,34]
[0,1,1,2,3,5,8,13,21,34,55]
[0,1,1,2,3,5,8,13,21,34,55,89]

Итак, вместо того, чтобы ждать, пока будет построен самый последний список (что будет никогда) и затем переворачивать его, почему бы не создавать его элементы по ходу дела? Во всяком случае, это все уже есть. И последний элемент каждого промежуточного результата, перевернутый - разве это не только его первый элемент?

> take 11 $ map (head.snd) $ iterate 
          (\(_:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])
[1,1,2,3,5,8,13,21,34,55,89]

Аккуратно, ага. Так действительно ли нам нужен явный счетчик времени? Нам нужно тащить за собой весь хвост предыдущего промежуточного результата, или нам нужны только его первые два элемента?

fibs = map (head.tail) $ iterate (\[x,y] -> [x+y,x]) [1,0]

Использование кортежей для списков постоянной длины будет немного чище. Итак, вы видите, что мы подошли к одному из канонических определений,

fibs = g (1,0)  where  g (a,b) = b : g (a+b,a)

(см. также В чем разница между рекурсией и corecursion?< /а>).

fibs4 = 0:[ b | (a, b) <- scanl (\(x,y) _ -> (y,x + y)) (0,1) [0..] ]

fibs4a = [a | (a,b) <- iterate (\(a,b) -> (b, a+b)) (0,1)]

Да, вы не можете перевернуть бесконечный массив.

Посмотри на это:

0,1,1,2,3,5,8,13,21,...
  0,1,1,2,3,5,8, 13...   +
----------------------
0,1,2,3,5,8,13,21,...

Как вы можете видеть из моей попытки показать взаимосвязь того, как последовательность Фибоначчи может быть сгенерирована с использованием самой себя, это довольно просто! Вы бы zipWith фибоначчи с его хвостами использовали функцию сложения!

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Для более подробной информации, вот расширение вышеизложенного.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs = 0 : 1 : zipWith (+) 0:1:? 1:?
fibs = 0 : 1 : (0+1) : zipWith (+) 1:? ?
fibs = 0 : 1 : 1 : zipWith (+) 1:1:? 1:?
fibs = 0 : 1 : 1 : 2 : zipWith (+) 1:2:? 2:?
fibs = 0 : 1 : 1 : 2 : 3 : zipWith (+) 2:3:? 3:?

до бесконечности... ? представляет собой thunk, еще не оцененную часть вычислений Haskell.