Практическое использование `foldl`

Сегодня, когда я работал над одним маленьким скриптом, я использовал foldl вместо foldl'. Я получил stack overflow, поэтому импортировал Data.List (foldl') и остался доволен этим. И это мой рабочий процесс по умолчанию с foldl. Просто используйте foldl', когда ленивая версия падает для оценки.

Real World Haskell говорит, что в большинстве случаев мы должны использовать foldl' вместо foldl. Foldr Foldl Foldl ' говорит, что

Обычно выбирают между foldr и foldl'.

...

Однако, если функция комбинирования ленива в своем первом аргументе, 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'.

П.С. Я знаю, что термин practical сложно дать определение, но я надеюсь, вы поймете, что я имею в виду.

P. P. S. Я понимаю, почему lazy foldl по умолчанию в haskell. Я никого не прошу сдвигать гору и делать строгую версию по умолчанию. Меня просто очень интересуют примеры эксклюзивного использования функции foldl :)

P. P. P. S. Что ж, любое интересное использование foldl приветствуется.


fold haskell foldleft
person d12frosted    schedule 19.09.2014    source источник
comment
Вместо того, чтобы просто избегать undefined, вы также можете использовать foldl, чтобы избежать потенциально дорогостоящих операций. Если ваша функция сворачивания завершается рано после успешной операции, вы можете избежать выполнения дорогостоящих вычислений из-за лени. Могут быть более понятные способы его написания (на ум приходят моноиды), но свертки могут быть полезны для оптимизации компилятора.   -  person bheklilr    schedule 20.09.2014
comment
Да, я думал об этом. Но не могу представить себе хороший пример такой функции.   -  person d12frosted    schedule 20.09.2014

Ответы (2)


arrow_upward
13
arrow_downward

Вот более практичный пример использования классической наивной реализации Фибоначчи для моделирования дорогостоящих вычислений:

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'), у нас фактически есть программа, которая останавливается, а не программа, которая никогда не остановится.

person bheklilr    schedule 19.09.2014
comment
Разве вам не лучше сделать это с помощью reverse, за которым следует foldr? Таким образом, вам не придется обрабатывать весь список. - person Tom Ellis; 20.09.2014
comment
@TomEllis Я не говорю, что это лучший способ, просто это пример того, как foldl может быть лучшим выбором. - person bheklilr; 20.09.2014
comment
Что ж, спасибо за ответ. Теперь у меня есть несколько интересных примеров использования foldl: D - person d12frosted; 22.09.2014
comment
@TomEllis reverse обрабатывает весь список. - person Jeremy List; 27.05.2015
comment
@JeremyList Это правда. Я не могу вспомнить, о чем думал! - person Tom Ellis; 28.05.2015

arrow_upward
5
arrow_downward

Я могу придумать один (хотя, возможно, это дает хороший код только с оптимизирующим компилятором):

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
person Joachim Breitner    schedule 19.09.2014
comment
Что ж, это действительно похоже на _ ? 0 = 0. Но в любом случае спасибо за еще один пример. - person d12frosted; 20.09.2014