Unknown - haskell-notes

посмотрим на них.

9.3 Аннотации строгости

Языки с ленивой стратегией вычислений называют не строгими (non-strict), а языки с энергичной стра-

тегией вычислений соответственно~– строгими.

Принуждение к СЗНФ с помощью seq

Мы говорили о том, что при вычислении по имени значения вычисляются только при сопоставлении с

образцом или в case-выражениях. Есть специальная функция seq, которая форсирует приведение к СЗНФ:

seq ::a ->b ->b

Она принимает два аргумента, при выполнении функции первый аргумент приводится к СЗНФ и затем

возвращается второй. Вернёмся к примеру с sum. Привести к СЗНФ число – означает вычислить его полностью.

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

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

sum’ =iter 0

whereiter res []

=res

iter res (a :as)

= letres’ =res +a

in

res’ ‘seq‘ iter res’ as

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

Сохраним результат в отдельном модуле Strict.hs и попробуем теперь вычислить значение, придётся

подождать:

Strict>sum’ [1 ..1e9]

И мы ждём, и ждём, и ждём. Но переполнения памяти не происходит. Это хорошо. Но давайте прервём

вычисления. Нажмём ctrl +c. Функция sum’ вычисляется, но вычисляется очень медленно. Мы можем су-

щественно ускорить её, если скомпилируем модуль Strict. Для компиляции модуля переключимся в его

текущую директорию и вызовем компилятор ghc с флагом –make:

ghc --make Strict

Появились два файла Strict.hi и Strict.o. Теперь мы можем загрузить модуль Strictв интерпретатор

и сравнить выполнение двух функций:

Strict>sum’ [1 ..1e6]

5.000005e11

(0.00 secs, 89133484 bytes)

Strict>sum [1 ..1e6]

5.000005e11

(0.57 secs, 142563064 bytes)

Обратите внимание на прирост скорости. Умение понимать в каких случаях стоит ограничить лень очень

важно. И в программах на Haskell тоже. Также компилировать модули можно из интерпретатора. Для этого

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

Strict> :!ghc --make Strict

[1 of1] Compiling Strict

( Strict.hs, Strict.o )

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

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

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

f $!a =a ‘seq‘ f a

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

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

sum’ =iter 0

whereiter res []

=res

iter res (a :as)

=flip iter as $!res +a

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

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

product’:

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

product’ =iter 1

whereiter res []

=res

iter res (a :as)

= letres’ =res *a

in

res’ ‘seq‘ iter res’ as

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

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

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

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

foldl’ op init =iter init

whereiter res []

=res

iter res (a :as)

= letres’ =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

whereiter res []

=res

iter res (a :as)

=iter (res ‘op‘ a) as

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