Порядок вычислений в Haskell

Излишняя ленивость

Рассмотрим следующий вариант реализации суммы чисел:

sum numbers = foldl (+) 0 numbers

-- что то же самое, что и
sum numbers = sumAcc 0 numbers
  where
    sumAcc acc []     = acc
    sumAcc acc (x:xs) = sumAcc (acc+x) xs

Это – в чистом виде хвостовая (циклическая) рекурсия. Будучи реализованной в любом языке с энергичным порядком вычислений, она расходует ровно столько памяти, сколько она должна была бы расходовать на первый взгляд: несколько байт на хранение аккумулятора и очередного числа плюс память на хранение генератора очередного входного числа. Но в Haskell ситуация иная:

sum (take 5 [1..])
foldl (+) 0 (take 5 [1..])
foldl (+) 0 (1 : take 4 [2..])
foldl (+) (0+1) (take 4 [2..])
foldl (+) (0+1) (2 : take 3 [3..])
foldl (+) ((0+1)+2) (take 3 [3..])
foldl (+) ((0+1)+2) (3 : take 2 [4..])
foldl (+) (((0+1)+2)+3) (take 2 [4..])
foldl (+) (((0+1)+2)+3) (4 : take 1 [5..])
foldl (+) ((((0+1)+2)+3)+4) (take 1 [5..])
foldl (+) ((((0+1)+2)+3)+4) (5 : take 0 [6..])
foldl (+) (((((0+1)+2)+3)+4)+5) (take 0 [6..])
foldl (+) (((((0+1)+2)+3)+4)+5) []
(((((0+1)+2)+3)+4)+5) -- требуется хранить пять чисел и пять отложенных операций!

Чтобы избежать хранения лишней информации, аккумулятор нужно вычислять до перехода к следующей итерации цикла. Для этого используется специальная функция foldl' из модуля Data.Foldable, определённая так:

foldl' f a []     = a
foldl' f a (x:xs) = let b = (f a x) in (b `seq` foldl' f b xs)

Комбинатор seq по смыслу аналогичен следующему определению:

seq x y = y

Тем не менее, у него есть особенность – его вычисление приводит к вычислению x перед тем, как y начнёт вычисляться. Поэтому foldl' более экономно вычисляет сумму, чем foldl:

foldl' (+) 0 (take 3 [1..])
foldl' (+) 0 (1 : take 2 [2..])
let b = (+) 0 1 in seq b (foldl' (+) b (take 2 [2..]))
let b = 1 in foldl' (+) b (take 2 [2..])
foldl' (+) 1 (take 2 [2..])
foldl' (+) 0 (2 : take 1 [3..])
let b = (+) 1 2 in seq b (foldl' (+) b (take 1 [3..]))
let b = 3 in foldl' (+) b (take 1 [3..])
foldl' (+) 3 (take 1 [3..])
foldl' (+) 0 (3 : take 0 [4..])
let b = (+) 3 3 in seq b (foldl' (+) b (take 0 [4..]))
let b = 6 in foldl' (+) b (take 0 [4..])
foldl' (+) 6 (take 0 [4..])
foldl' (+) 6 []
6

Подобное применение seq довольно распространено, и поэтому существует специальное расширение языка BangPatterns, позволяющее помечать аргументы функции, которые следует вычислить перед вычислением значения:

{-# LANGUAGE BangPatterns #-}

-- теперь определение foldl' выглядит совсем просто!
foldl' f a [] = a
foldl' f !a (x:xs) = foldl' f (f a x) xs

Предостережение: поскольку выражение seq a равносильно id, компилятор имеет привычку в целях оптимизации менять порядок таких выражений друг относительно друга. Например, программа

main = seq (error "a") $ seq (error "b") $ pure ()

спокойно может напечатать "b" вместо "a". Единственное, что гарантируется компилятором – что они не будут выкинуты, и что их несущественные аргументы будут вычислены до того, как будет вычислен существенный аргумент (хотя, вообще говоря, даже это не гарантируется стандартом языка; тем не менее, все существующие компиляторы всё-таки дают такие гарантии).

Если требуется зачем-то задать явную последовательность вычислений, можно применить конструкцию наподобие

case a `seq` () of () -> b

но более идиоматично будет воспользоваться комбинатором pseq из модуля Control.Parallel – оптимизатор не трогает pseq.

Ещё одна тонкость: следует проявлять аккуратность при обработке очень больших объёмов данных (например, превышающих размер оперативной памяти). Оптимизатор иногда выносит константы на более высокие уровни, преобразуя, например, код

largeNumber n = foldl' (+) 0 (take n [1..])

в нечто наподобие

list = [1..]
op   = \x y -> x + y
zero = 0

largeNumber n = foldl' op zero (take n list)

Такое преобразование потенциально уменьшает количество раз, которое список пересчитывается заново, но после вычисления части списка требует память для хранения этой части. Конечно, приведённый код исправляется тривиально:

largeNumber n = foldl' (+) 0 [1..n]

Тем не менее, бывают ситуации, в которых подобное исправление произвести затруднительно. Рекомендуется в первую очередь воспользоваться директивой

{-# INLINE largeNumber #-}

В тех случаях, когда и это не помогает, можно в начале программы поставить директиву

{-# OPTIONS_GHC -fno-full-laziness #-}

которая отключает вышеописанное поведение оптимизатора.