Изучай Haskell во имя добра! (Липовача) - страница 71
>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'.
Поищем числа
Вы прогуливаетесь по улице, и тут к вам подходит старушка и спрашивает: «Простите, а каково первое натуральное число, сумма цифр которого равна 40?»
Ну что, сдулись? Давайте применим Haskell-магию и найдём это число. Если мы, к примеру, просуммируем цифры числа 123, то получим 6. У какого же числа тогда сумма цифр равна 40?
Первым делом напишем функцию, которая считает сумму цифр заданного числа. Внимание, хитрый трюк! Воспользуемся функцией >show и преобразуем наше число в строку. Когда у нас будет строка из цифр, мы переведём каждый её символ в число и просуммируем получившийся числовой список. Превращать символ в число будем с помощью функции