Еще немного про строгие функции

Возможно, этот раздел покажется вам немножко сложноватым. Давайте договоримся так: как только вы теряете нить объяснений – сразу бросайте это безнадежное дело, и переходите к следующему разделу. А сюда вернетесь тогда, когда ваши функции вдруг оказываются ужасно неэффективными (по времени или памяти) тогда, когда к этому, вроде бы, никаких предпосылок нет. Договорились?

Помните, мы говорили, что все функции в Haskell – нестрогие и ленивые? Вот у функции ($) есть специальный аналог ($!):

($) :: (a -> b) -> a -> b

($!) :: (a -> b) -> a -> b

Функция ($), как мы помним – это просто применение функции. Так вот, функция ($!) – это тоже просто применение функции, но – строгое. То есть, если функция ($) f x просто скажет что-то типа "эй, функция f, вот тебе x, дай-ка мне твой результат?", то функция ($!) f x сначала вычислит x, а потом уже передаст его функции f.

Тут можно было бы нарисовать смешной диалог. Если спросить у обычной функции (+): "Чему будет равно (+) 5 6 ?", – ленивая функция ответит: "5+6". А вот если был бы строгий аналог функции (+), он бы ответил честно: 11.

Как бы эту разницу увидеть? А вот, например, так:

SomeModule> length (take 10 (repeat $ (1/0)))

10

SomeModule> length (take 10 (repeat $! (1/0)))

Program error: {primDivDouble 1.0 0.0}

Что происходит в первом случае? Функция repeat создает целый список из нетерминальных выражений 1/0, мы потом пытаемся выбрать 10 элементов, и считаем, сколько выбралось. Как и положено ленивым функциям, результат вычисляется нормально, потому что repeat и не думает вычислять 1/0 – оно ей надо?

Зато во втором случае, оператор строгого применения ($!) вычисляет 1/0 перед тем, как передать его функции repeat, и, разумеется, вычисление обрывается с ошибкой.

Однако, при этом:

head [2, (1/) $! 0] → 2.0

length $! [map sin [1..]] → 1

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

Как правило, мы не будем сталкиваться с необходимостью делать строгие функции вместо нестрогих. Но вы можете столкнуться с тем, что при вычислении очень глубокой рекурсии (даже и хвостовой), накапливаемый параметр разбухает так, что не умещается в стеке и программа падает – или не падает, но просто очень неэффективно работает. Попробуйте, например, вычислить выражение foldl (+) 0 [1..100000]? Казалось бы, чего там – просто посчитать сумму первых ста тысяч натуральных чисел – а ваш простой интерпретатор может и не справиться. Почему, ведь функция foldl даже реализована с использованием хвостовой рекурсии!

foldl :: (a -> b -> a) -> a -> [b] -> a

foldl f z [] = z

foldl f z (x:xs) = foldl f (f z x) xs

Проблема в том, что наш ленивый язык накапливает в аккумуляторе не частичные суммы (1,3,6,10,...) а конструкцию вида (((0+1)+2)+3)+... , в надежде, что эту сумму не придется вычислять. Но мы-то знаем, что придется! Для этого есть строгая версия функции foldl, которая отличается от нее только апострофом в названии (апостроф сам по себе к строгости отношения не имеет – он считается просто обычной буквой):

foldl' :: (a -> b -> a) -> a -> [b] -> a

foldl' f a [] = a

foldl' f a (x:xs) = (foldl' f $! f a x) xs

Для сравнения, перепишем немного определение функции foldl, чтобы очевидна стала разница (вы же видите, что это то же самое определение, что и абзацем назад?):

foldl :: (a -> b -> a) -> a -> [b] -> a

foldl f z [] = z

foldl f z (x:xs) = (foldl f $ (f z x)) xs

На каждом шаге функция foldl' действительно вычисляет новое значение аккумулятора, а не накапливает там ленивую очередь из вызовов! Проверьте, выражение foldl' (+) 0 [1..100000] вычисляется легко (чтобы воспользоваться функций foldl', придется, возможно, подключить модуль Data.List).