Unknown - haskell-notes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

mean ::[ Double] -> Double

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

wherecount

(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)

whereiter res

[]

=res

iter (sum, leng)

(a :as)

=

lets =sum

+a

l =leng +1

in

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

division (sum, leng) =sum /fromIntegral leng

Аннотации строгости | 149

Такой вот монстр. Функция seq право ассоциативна поэтому скобки будут группироваться в нужном

порядке. В этом определении мы просим вычислитель привести к СЗНФ числа , а не пары чисел, как в прошлой

версии. Для чисел СЗНФ совпадает с НФ, и всё должно пройти гладко, но сохраним это определение и

проверим результат:

Prelude Strict> :!ghc --make Strict

[1 of1] Compiling Strict

( Strict.hs, Strict.o )

Prelude Strict> :load Strict

Ok, modules loaded : Strict.

(0.00 secs, 0 bytes)

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

5000000.5

(0.65 secs, 1083157384 bytes)

Получилось! Скорость чуть хуже чем у sum’, но не в сто раз.

Энергичные образцы

В GHC предусмотрены специальные обозначения для принудительного приведения выражения к СЗНФ.

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

подключить их. Расширения подключаются с помощью специального комментария в самом начале модуля:

{-# LANGUAGE BangPatterns #-}

Эта запись активирует расширение языка с именем BangPatterns. Ядро языка Haskell фиксировано стан-