О строгих левых свёртках

В предыдущей главе мы видели, как работает функция foldl и как с её помощью реализовывать всякие крутые функции. Правда, мы пока не исследовали одну связанную с foldl ловушку: её использование иногда может приводить к так называемым ошибкам переполнения стека, которые случаются, если программе требуется слишком много места в одном специальном разделе памяти (в сегменте стека). Проиллюстрируем проблему, воспользовавшись свёрткой с функцией + для суммирования списка из сотни единиц:

ghci> foldl (+) 0 (replicate 100 1)

100

Пока всё работает. Но что если сделать то же самое для списка, содержащего, спасибо доктору Зло, один миллион единиц?

ghci> foldl (+) 0 (replicate 1000000 1)

*** Exception: stack overflow

Ого, жестоко! Что же случилось? Haskell ленив, поэтому он откладывает реальные вычисления настолько, насколько возможно. Когда мы используем foldl, Haskell не вычисляет аккумулятор на каждом шаге. Вместо этого он откладывает вычисление. На каждом следующем шаге он снова ничего не считает, опять откладывая на потом. Ему, правда, приходится сохранять старое отложенное вычисление в памяти, потому что новому может потребоваться его результат. Таким образом, пока свёртка foldl радостно торопится по списку, в памяти образуется куча отложенных вычислений, каждое из которых занимает некоторый объём памяти. Рано или поздно это может привести к ошибке переполнения стека.

Вот как Haskell вычисляет выражение foldl (+) 0 [1,2,3]:

foldl (+) 0 [1,2,3] =

foldl (+) (0 + 1) [2,3] =

foldl (+) ((0 + 1) + 2) [3] =

foldl (+) (((0 + 1) + 2) + 3) [] =

((0 + 1) + 2) + 3 =

(1+2) + 3 =

3 + 3 =

6

Здесь видно, что сначала строится большой стек из отложенных вычислений. Затем, по достижении конца списка, начинаются реальные вычисления. Для маленьких списков никакой проблемы нет, а вот если список громадный, с миллионом элементов или даже больше, вы и получите переполнение стека. Дело в том, что все эти отложенные вычисления выполняются рекурсивно. Было бы неплохо, если бы существовала функция, которая вычисления не откладывает, правда же? Она бы работала как-то так:

foldl' (+) 0 [1,2,3] =

foldl' (+) 1 [2,3] =

foldl' (+) 3 [3] =

foldl (+) 6 [] =

6

Вычисления между шагами свёртки не откладываются – они тут же выполняются. Ну что ж, нам повезло: строгая версия функции foldl в модуле Data.List есть, и называется она именно foldl'. Попробуем-ка с её помощью вычислить сумму миллиона единиц:

ghci> foldl' (+) 0 (replicate 1000000 1)

1000000

Потрясающий успех! Так что, если, используя foldl, получите ошибку переполнения стека, попробуйте переключиться на foldl'. Кстати, у foldl1 тоже есть строгая версия, она называется foldl1'.