Можно ли использовать fold для создания бесконечных списков?
Я написал следующий код, который создает бесконечный список чисел Фибоначчи:
fibs = 1:1:fib 1 1
where fib a b = a+b:fib b (a+b)
Можно ли написать приведенный выше код, используя foldl
или же foldr
избежать рекурсии?
4 ответа
Я не знаю, возможно ли создавать бесконечные списки с foldl
, Вы могли бы решить эту проблему, используя foldr
, но тогда вам придется создать еще один список, чтобы свернуть. Каким будет этот список? В числах Фибоначчи нет ничего, что предполагало бы, что они генерируются из какого-то другого списка.
Вместо этого вы хотите использовать unfoldr
, Его можно использовать для создания списков вместо их использования, как в случае с foldl
а также foldr
, Вот как бы вы использовали unfoldr
генерировать бесконечный список чисел Фибоначчи.
fib = unfoldr (\(a,b) -> Just (a,(b,a+b))) (1,1)
Ты можешь найти unfoldr
в модуле Data.List
в базовом пакете.
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
что ближе к определению в вопросе.)
хотя это наблюдение, хотя и верно, вряд ли указывает на здоровый стиль программирования.
Одним из способов избежать явной рекурсии является использование 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)
Ты можешь использовать 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
не будет работать даже и он будет работать вечно.