Можно ли использовать fold для создания бесконечных списков?

Question

Я написал следующий код, который создает бесконечный список чисел Фибоначчи:

fibs = 1:1:fib 1 1
  where fib a b = a+b:fib b (a+b)

Можно ли написать приведенный выше код, используя foldl или же foldr избежать рекурсии?

Answer 1

Я не знаю, возможно ли создавать бесконечные списки с foldl, Вы могли бы решить эту проблему, используя foldr, но тогда вам придется создать еще один список, чтобы свернуть. Каким будет этот список? В числах Фибоначчи нет ничего, что предполагало бы, что они генерируются из какого-то другого списка.

Вместо этого вы хотите использовать unfoldr, Его можно использовать для создания списков вместо их использования, как в случае с foldl а также foldr, Вот как бы вы использовали unfoldr генерировать бесконечный список чисел Фибоначчи.

fib = unfoldr (\(a,b) -> Just (a,(b,a+b))) (1,1)

Ты можешь найти unfoldr в модуле Data.List в базовом пакете.

Answer 2

foldl а также foldr функции являются спискомпотребителей. Как справедливо указывает ответ Свеннингсона, unfoldr является списком-производителем, который подходит для захвата ко- рекурсивной структуры fibs,

Однако, учитывая, что foldl а также foldr являются полиморфными в своих типах возвращаемых данных, то есть в том, что они производят, используя список, разумно спросить, могут ли они использоваться для использования одного списка и создания другого. Может ли любой из этих созданных списков быть бесконечным?

Глядя на определение foldl

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a []        = a
foldl f a (b : bs)  = foldl f (f a b) bs

мы видим это для foldl чтобы произвести что-либо вообще, список, который он потребляет, должен быть конечным. Таким образом, если foldl f a производит бесконечный выход, потому что a бесконечен или потому что f иногда выполняет бесконечную генерацию списка.

Это другая история с foldr

foldr :: (b -> a -> a) -> a -> [b] -> a
foldr f a []        = a
foldr f a (b : bs)  = f b (foldr f a bs)

который допускает ленивую возможность того, что f может генерировать некоторый выход для каждого b потребляется от входа. Операции как

map g = foldr (\ b gbs -> g b : gbs) []   -- golfers prefer ((:) . g)
stutter = foldr (\ x xxs -> x : x : xxs) []

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

Таким образом, дерзкий человек может выразить любую бесконечную рекурсию как нерекурсивную foldr в бесконечном списке. Например,

foldr (\ _ fibs -> 1 : 1 : zipWith (+) fibs (tail fibs)) undefined [1..]

(Изменить: или, в этом отношении

foldr (\_ fib a b -> a : fib b (a + b)) undefined [1..] 1 1

что ближе к определению в вопросе.)

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

Answer 3

Одним из способов избежать явной рекурсии является использование fix выразить рекурсию как фиксированную точку.

import Data.Function (fix)

fibs = fix $ \l -> [1,1] ++ zipWith (+) l (tail l)

или в бессмысленном стиле

import Data.Function (fix)
import Control.Monad.Instances

fibs = fix $ ([1,1] ++) . (zipWith (+) =<< tail)

Answer 4

Ты можешь использовать zipWith написать свое определение

fibonacci = 1:1:zipWith (+) fibonacci (tail fibonacci)

редактировать: хорошо, я не думаю, что вы можете использовать foldl или foldr для создания бесконечного списка. Не в любом простом мыслимом смысле. Если вы посмотрите на простое определение фолд

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldl никогда не вернется, пока не исчерпает весь список. Итак, простой пример, как

g = foldl f [] [1..]
 where 
  f xs a = xs ++ [a]

> take 10 g

не будет работать даже и он будет работать вечно.