Учебник по Haskell

воспользуемся командой :! , она выполняет системные команды в интерпретаторе ghci:

Strict> :! ghc --make Strict

[1 of 1] Compiling Strict

( Strict. hs, Strict. o )

Отметим наличие специальной функции применения, которая просит перед применением привести ар-

гумент к СЗНФ, эта функция определена в Prelude:

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

f $! a = a ‘seq‘ f a

С этой функцией мы можем определить функцию sum так:

sum’ :: Num a => [a] -> a

sum’ = iter 0

where iter res []

= res

iter res (a:as)

= flip iter as $! res + a

Функции с хвостовой рекурсией

Определим функцию, которая не будет лениться при вычислении произведения чисел, мы назовём её

product’:

product’ :: Num a => [a] -> a

product’ = iter 1

where iter res []

= res

iter res (a:as)

= let res’ = res * a

in

res’ ‘seq‘ iter res’ as

Смотрите функция sum изменилась лишь в двух местах. Это говорит о том, что пора задуматься о том,

а нет ли такой общей функции, которая включает в себя и то и другое поведение. Такая функция есть и

называется она foldl’, вот её определение:

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

foldl’ op init = iter init

where iter res []

= res

iter res (a:as)

= let res’ = res ‘op‘ a

in

res’ ‘seq‘ iter res’ as

Мы вынесли в аргументы функции бинарную операцию и начальное значение. Всё остальное осталось

прежним. Эта функция живёт в модуле Data.List. Теперь мы можем определить функции sum’ и prod’:

148 | Глава 9: Редукция выражений

sum’

= foldl’ (+) 0

product’

= foldl’ (*) 1

Также в Prelude определена функция foldl. Она накапливает значения в аргументе, но без принуждения

вычислять промежуточные результаты:

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

foldl op init = iter init

where iter res []

= res

iter res (a:as)

= iter (res ‘op‘ a) as

Такая функция называется функцией с хвостовой рекурсией (tail-recursive function). Рекурсия хвостовая

тогда, когда рекурсивный вызов функции является последним действием, которое выполняется в функции.

Посмотрите на второе уравнение функции iter. Мы вызываем функцию iter рекурсивно последним делом. В

языках с вычислением по значению часто хвостовая рекурсия имеет преимущество за счёт экономии памяти

(тот момент который мы обсуждали в самом начале). Но как видно из этого раздела в ленивых языках это не

так. Библиотечная функция sum будет накапливать выражения перед вычислением с риском исчерпать всю

доступную память, потому что она определена через foldl.

Тонкости применения seq

Хочу подчеркнуть, что функция seq не вычисляет свой первый аргумент полностью. Первый аргумент

не приводится к нормальной форме. Мы лишь просим вычислитель узнать какой конструктор находится в

корне у данного выражения. Например в выражении isZero $! infinity знак $! ничем не отличается от

простого применения мы и так будем приводить аргумент infinity к СЗНФ, когда нам понадобится узнать

какое из уравнений для isZero выбрать, ведь в аргументе функции есть сопоставление с образцом.

Посмотрим на один типичный пример. Вычисление среднего для списка чисел. Среднее равно сумме

всех элементов списка, разделённой на длину списка. Для того чтобы вычислить значение за один проход

мы будем одновременно вычислять и сумму элементов и значение длины. Также мы понимаем, что нам не

нужно откладывать вычисления, воспользуемся функцией foldl’:

mean :: [Double] -> Double

mean = division . foldl’ count (0, 0)

where count

(sum, leng) a = (sum+a, leng+1)

division (sum, leng) = sum / fromIntegral leng

Проходим по списку, копим сумму в первом элементе пары и длину во втором. В самом конце делим

первый элемент на второй. Обратите внимание на функцию fromIntegral она преобразует значения из це-

лых чисел, в какие-нибудь другие из класса Num. Сохраним это определение в модуле Strict скомпилируем

модуль и загрузим в интерпретатор, не забудьте импортировать модуль Data.List, он нужен для функции

foldl’. Посмотрим, что у нас получилось:

Prelude Strict> mean [1 .. 1e7]

5000000.5

(49.65 secs, 2476557164 bytes)

Получилось очень медленно, странно ведь порядок этой функции должен быть таким же что и у sum’.

Посмотрим на скорость sum’:

Prelude Strict> sum’ [1 .. 1e7]

5.0000005e13

(0.50 secs, 881855740 bytes)

В 100 раз быстрее. Теперь представьте, что у нас 10 таких функций как mean они разбросаны по всему

коду и делают своё чёрное ленивое дело. Причина такого поведения кроется в том, что мы опять завернули

значение в другой тип, на этот раз в пару. Когда вычислитель дойдёт до seq, он остановится на выражении

(thunk, thunk) вместо двух чисел. Он вновь будет накапливать отложенные вычисления, а не значения.

Перепишем mean, теперь мы будем вычислять значения пары по отдельности и попросим вычислитель

привести к СЗНФ каждое из них перед вычислением итогового значения:

mean’ :: [Double] -> Double

mean’ = division . iter (0, 0)

where iter res

[]

= res

iter (sum, leng)

(a:as)

=

let s = sum

+ a

l = leng + 1

in

s ‘seq‘ l ‘seq‘ iter (s, l) as