Практическое использование `foldl`
Сегодня, когда я работал над одним маленьким script, я использовал foldl вместо foldl'. Я получил stack overflow, поэтому я импортировал Data.List (foldl') и был доволен этим. И это мой рабочий процесс по умолчанию с foldl. Просто используйте foldl', когда ленивая версия падает для оценки.
Real World Haskell говорит, что в большинстве случаев мы должны использовать foldl' вместо foldl. Foldr Foldl Foldl говорит, что
Обычно выбор между foldr и foldl'.
...
Однако, если функция объединения lazy в своем первом аргументе, foldl может с радостью вернуть результат, в котором foldl' попадает в исключение.
И приведенный пример:
(?) :: Int -> Int -> Int
_ ? 0 = 0
x ? y = x*y
list :: [Int]
list = [2, 3, undefined, 5, 0]
okey = foldl (?) 1 list
boom = foldl' (?) 1 list
Ну, извините, но это скорее академический, интересный, но академический пример. Поэтому я спрашиваю, есть ли пример практического использования foldl? Я имею в виду, когда мы не можем заменить foldl на foldl'.
Р. S. Я знаю, трудно определить термин practical, но я надеюсь, вы поймете, что я имею в виду.
Р. P. S. Я понимаю, почему lazy foldl является дефолтом в haskell. Я не прошу никого переместить гору и сделать строгую версию по умолчанию. Меня просто интересуют примеры исключительного использования функции foldl:)
Р. P. P. S. Ну, любое интересное использование foldl приветствуется.
Ответы
Ответ 1
Вот более практичный пример использования классической наивной реализации Фибоначчи для моделирования дорогостоящих вычислений:
fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
f :: Int -> Int -> Int
f a b = if b < 1000 then b else min b a
Тогда, если у вас
> -- Turn on statistics for illustrative purposes
> :set +s
> foldl f maxBound $ map fib [30, 20, 15]
987
(0.02 secs, 0 bytes)
> foldl' f maxBound $ map fib [30, 20, 15]
987
(4.54 secs, 409778880 bytes)
Здесь мы имеем резкую разницу в производительности исполнения между ленивыми и строгими версиями, при этом ленивая версия выигрывает от оползня. Конечно, ваши номера могут отличаться для вашего компьютера, но вы определенно заметите разницу в скорости выполнения. foldl' заставляет каждое вычисление встречаться, а foldl - нет. Это также может быть полезно для чего-то вроде
> foldl f maxBound $ map length [repeat 1, repeat 1, replicate 10 1]
10
В отличие от примера fib, это вычисление технически связано с дном, так как length $ repeat 1 никогда не закончит вычисление. Не имея обоих аргументов f строго (как foldl'), у нас фактически есть программа, которая останавливается против той, которая никогда не будет.
Ответ 2
Я могу думать об одном (хотя, возможно, это дает хороший код только с оптимизирующим компилятором):
last = foldl (\_ x -> x) (error "emptyList")
У него не было бы правильного поведения с foldl':
> foldl (\_ x -> x) (error "emptyList") [error "foo", "last"]
"last"
> foldl' (\_ x -> x) (error "emptyList") [error "foo", "last"]
"*** Exception: foo
