Помните, в Haskell вы можете использовать бесконечные списки из-за ленивых вычислений. Итак, head [1..] - это всего лишь 1, а head $ map (+1) [1..] - это 2, хотя `[1 ..] бесконечно долго. Если вы этого не понимаете, остановитесь и поиграйте с ним некоторое время. Если вы это понимаете, читайте дальше ...
Я думаю, что часть вашей путаницы заключается в том, что foldl и foldr всегда начинаются с одной или другой стороны, поэтому вам не нужно указывать длину.
foldr имеет очень простое определение
foldr _ z [] = z
foldr f z (x:xs) = f x $ foldr f z xs
почему это может заканчиваться в бесконечных списках, попробуйте
dumbFunc :: a -> b -> String
dumbFunc _ _ = "always returns the same string"
testFold = foldr dumbFunc 0 [1..]
здесь мы передаем foldr a "" (поскольку значение не имеет значения) и бесконечный список натуральных чисел. Это заканчивается? Да.
Причина, по которой он заканчивается, в том, что оценка Хаскелла эквивалентна ленивому переписыванию термина.
Итак
testFold = foldr dumbFunc "" [1..]
становится (для разрешения сопоставления с образцом)
testFold = foldr dumbFunc "" (1:[2..])
, что совпадает с (из нашего определения сгиба)
testFold = dumbFunc 1 $ foldr dumbFunc "" [2..]
теперь по определению dumbFunc мы можем сделать вывод
testFold = "always returns the same string"
Это более интересно, когда у нас есть функции, которые что-то делают, но иногда ленивы. Например
foldr (||) False
используется для определения, содержит ли список какие-либо элементы True. Мы можем использовать это для определения функции более высокого порядка n any, которая возвращает True тогда и только тогда, когда переданная функция имеет значение true для некоторого элемента списка
any :: (a -> Bool) -> [a] -> Bool
any f = (foldr (||) False) . (map f)
Хорошая особенность ленивых вычислений в том, что они остановятся, когда встретят первый элемент e такой, что f e == True
С другой стороны, это не относится к foldl. Зачем? Ну очень просто foldl выглядит как
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Теперь, что случилось бы, если бы мы попробовали наш пример выше
testFold' = foldl dumbFunc "" [1..]
testFold' = foldl dumbFunc "" (1:[2..])
теперь это становится:
testFold' = foldl dumbFunc (dumbFunc "" 1) [2..]
так
testFold' = foldl dumbFunc (dumbFunc (dumbFunc "" 1) 2) [3..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) [4..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) 4) [5..]
и так далее и тому подобное. Мы никогда никуда не доберемся, потому что Haskell всегда сначала оценивает внешнюю функцию (это в двух словах - ленивая оценка).
Одним из классных следствий этого является то, что вы можете реализовать foldl из foldr, но не наоборот. Это означает, что в некотором смысле foldr является самой фундаментальной из всех строковых функций более высокого порядка, поскольку мы используем ее для реализации почти всех остальных. Вы все еще можете использовать foldl иногда, потому что вы можете реализовать рекурсивный foldl хвост и получить от этого некоторое повышение производительности.