В этой главе мы поговорим о том как вычисляются программы. В самом начале мы говорили о том, что процесса вычисления значений нет. В том смысле, что у нас нет новых значений, у нас ничего не меняется, мы лишь расшифровываем синонимы значений.
Вкратце вспомним то, что мы уже знаем о вычислениях. Сначала мы с помощью типов определяем множество всех возможных значений. Значения – это деревья в узлах которых записаны конструкторы, которые мы определяем в типах. Так например мы можем определить тип:
data Nat = Zero | Succ Nat
Этим типом мы определяем множество допустимых значений. В данном случае это цепочки конструкторов Succ, которые заканчиваются конструктором Zero:
Zero, Succ Zero, Succ (Succ Zero), ...
Затем начинаем давать им новые имена, создавая константы (простые имена-синонимы)
zero = Zero one = Succ zero two = Succ one
и функции (составные имена-синонимы):
foldNat :: a -> (a -> a) -> Nat -> a foldNat z s Zero = z foldNat z s (Succ n) = s (foldNat z s n) add a = foldNat a Succ mul a = foldNat one (add a)
Затем мы передаём нашу программу на проверку компилятору. Мы просим у него проверить не создаём ли мы случайно какие-нибудь бессмысленные выражения. Бессмысленные потому, что они пытаются создать значение, которое не вписывается в наши типы. Например если мы где-нибудь попробуем составить выражение:
add Zero mul
Компилятор напомнит нам о том, что мы пытаемся подставить функцию mul на место обычного значения типа Nat. Тогда мы исправим выражение на:
add Zero two
Компилятор согласится. И передаст выражение вычислителю. И тут мы говорили, что вычислитель начинает проводить расшифровку нашего описания. Он подставляет на место синонимов их определения, правые части из уравнений. Этот процесс мы называли редукцией. Вычислитель видит два синонима и одно значение. С какого синонима начать? С add или two?
Этот вопрос приводит нас к понятию стратегии вычислений. Поскольку вычисляем мы только константы, то наше выражение также можно представить в виде дерева. Только теперь у нас в узлах записаны не только конструкторы, но и синонимы. Процесс редукции можно представить как процесс очистки такого дерева от синонимов. Посмотрим на дерево нашего значения:
Оказывается у нас есть две возможности очистки синонимов.
начинаем с листьев и убираем все синонимы в листьях дерева выражения. Как только в данном узле и всех дочерних узлах остались одни конструкторы можно переходить на уровень выше. Так мы поднимаемся выше и выше пока не дойдём до корня.
начинаем с корня, самого внешнего синонима и заменяем его на определение (с помощью уравнения на правую часть от знака равно), если на верху снова окажется синоним, мы опять заменим его на определение и так пока на верху не появится конструктор, тогда мы спустимся в дочерние деревья и будем повторять эту процедуру пока не дойдём до листьев дерева.
Посмотрим как каждая из стратегий будет редуцировать наше выражение. Начнём со стратегии от листьев к корню (снизу-вверх):
add Zero two
-- видим два синонима add и two
-- раскрываем two, ведь он находится ниже всех синонимов
=> add Zero (Succ one)
-- ниже появился ещё один синоним, раскроем и его
=> add Zero (Succ (Succ zero))
-- появился синоним zero раскроем его
=> add Zero (Succ (Suсс Zero))
-- все узлы ниже содержат конструкторы, поднимаемся вверх до синонима
-- заменяем add на его правую часть
=> foldNat Succ Zero (Succ (Succ Zero))
-- самый нижний синоним foldNat, раскроем его
-- сопоставление с образцом проходит во втором уравнении для foldNat
=> Succ (foldNat Succ Zero (Succ Zero))
-- снова раскрываем foldNat
=> Succ (Succ (foldNat Zero Zero))
-- снова раскрываем foldNat, но на этот раз нам подходит
-- первое уравнение из определения foldNat
=> Succ (Succ Zero)
-- синонимов больше нет можно вернуть значение
-- результат:
Succ (Succ Zero)
В этой стратегии для каждой функции мы сначала вычисляем до конца все аргументы, потом подставляем расшифрованные значения в определение функции.
Теперь посмотрим на вычисление от корня к листьям (сверху-вниз):
add Zero two -- видим два синонима add и two, начинаем с того, что ближе всех к корню => foldNat Succ Zero two -- теперь выше всех foldNat, раскроем его
Но для того чтобы раскрыть foldNat нам нужно узнать какое уравнение выбрать для этого нам нужно понять какой конструктор находится в корне у второго аргумента, если это Zero, то мы выберем первое уравнение, а если это Succ, то второе:
-- в уравнении для foldNat видим декомпозицию по второму
-- аргументу. Узнаем какой конструктор в корне у two
=> foldNat Succ Zero (Succ one)
-- Это Succ нам нужно второе уравнение:
=> Succ (foldNat Succ Zero one)
-- В корне м ыполучили конструктор, можем спуститься ниже.
-- Там мы видим foldNat, для того чтобы раскрыть его нам
-- снова нужно понять какой конструктор в корне у второго аргумента:
=> Succ (foldNat Succ Zero (Succ zero))
-- Это опять Succ переходим ко второму уравнению для foldNat
=> Succ (Succ (foldNat Succ Zero zero))
-- Снова раскрываем второй аргумент у foldNat
=> Succ (Succ (foldNat Succ Zero Zero))
-- Ага это Zero, выбираем первое уравнение
=> Succ (Succ Zero)
-- Синонимов больше нет можно вернуть значение
-- результат:
Succ (Succ Zero)
В этой стратегии мы всегда раскрываем самый верхний уровень выражения, можно представить как мы вытягиваем конструкторы от корня по цепочке. У этих стратегий есть специальные имена:
вычисление по значению (call by value), когда мы идём от листьев к корню.
вычисление по имени (call by name), когда мы идём от корня к листьям.
Отметим, что стратегию вычисления по значению также принято называть энергичными вычислениями (eqger evaluation) или аппликативной (applicative) стратегией редукции. Вычисление по имени также принято называть нормальной (normal) стратегией редукции.
В чём преимущества, той и другой стратегии.
Если выражение вычисляется полностью, первая стратегия более эффективна по расходу памяти.
Вычисляется полностью означает все компоненты выражения участвуют в вычислении. Например то выражении, которое мы рассмотрели так подробно, вычисляется полностью. Приведём пример выражения, при вычислении которого нужна лишь часть аргументов, для этого определим функцию:
isZero :: Nat -> Bool isZero Zero = True isZero _ = False
Она проверяет является ли нулём данное число, теперь представим как будет вычисляться выражение, в той и другой стратегии:
isZero (add Zero two)
Первая стратегия сначала вычислит все аргументы у add потом расшифрует add и только в самом конце доберётся до isZero. На это уйдёт восемь шагов (семь на вычисление add Zero two). В то время как вторая стратегия начнёт с isZero. Для вычисления isZero ей потребуется узнать какой конструктор в корне у выражения add Zero two. Она узнает это за два шага. Итого три шага. Налицо экономия усилий.
Почему вторая стратегия экономит память? Поскольку мы всегда вычисляем аргументы функции, мы можем не хранить описания в памяти а сразу при подстановке в функцию начинать редукцию. Эту ситуацию можно понять на таком примере, посчитаем сумму чисел от одного до четырёх с помощью такой функции:
sum :: Int -> [Int] -> Int sum [] res = res sum (x:xs) res = sum xs (res + x)
Посмотрим на то как вычисляет первая стратегия, с учётом того что мы вычисляем значения при подстановке:
sum [1,2,3,4] 0 => sum [2,3,4] (0 + 1) => sum [2,3,4] 1 => sum [3,4] (1 + 2) => sum [3,4] 3 => sum [4] (3+3) => sum [4] 6 => sum [] (6+4) => sum [] 10 => 10
Теперь посмотрим на вторую стратегию:
sum [1,2,3,4] 0 => sum [2,3,4] 0+1 => sum [3,4] (0+1)+2 => sum [4] ((0+1)+2)+3 => sum [] (((0+1)+2)+3)+4 => (((0+1)+2)+3)+4 => ((1+2)+3)+4 => (3+3)+4 => 6+4 => 10
А теперь представьте, что мы решили посчитать сумму чисел от 1 до миллиона. Сколько вычислений нам придётся накопить! В этом недостаток второй стратегии. Но есть и ещё один недостаток, рассмотрим выражение:
(\x -> add (add x x) x) (add Zero two)
Первая стратегия сначала редуцирует выражение add Zero two в то время как вторая подставит это выражение в функцию и утроит свою работу!
Но у второй стратегии есть одно очень веское преимущество, она может вычислять больше выражений чем вторая. Определим значение бесконечность:
infinity :: Nat infinity = Succ infinity
Это рекурсивное определение, если мы попытаемся его распечатать мы получим бесконечную последовательность Succ. Чем не бесконечность? Теперь посмотрим на выражение:
isZero infinity
Первая стратегия захлебнётся, вычисляя аргумент функции isZero, в то время как вторая найдёт решение за два шага.
Подведём итоги. Плюсы вычисления по значению:
Эффективный расход памяти в том случае если все
составляющие выражения участвуют в вычислении.
Она не может дублировать вычисления, как стратегия вычисления по имени.
Плюсы вычисления по имени:
Меньше вычислений в том случае, если при вычислении выражения
участвует лишь часть составляющих.
Большая выразительность. Мы можем вычислить больше значений.
Какую из них выбрать? В Haskell пошли по второму пути. Всё-таки преимущество выразительности языка оказалось самым существенным. Но для того чтобы избежать недостатков стратегии вычисления по имени оно было модифицировано. Давайте посмотрим как.
Вернёмся к выражению:
(\x -> add (add x x) x) (add Zero two)
Нам нужно как-то рассказать функции о том, что имя x в её теле указывает на одно и то же значение. И если в одном из x значение будет вычислено переиспользовать эти результаты в других x. Вместо значения мы будем передавать в функцию ссылку на область памяти, которая содержит рецепт получения этого значения. Напомню, что мы по-прежнему вычисляем значение сверху вниз, сейчас мы просто хотим избавиться от проблемы дублирования. Вернитесь к примеру с вычислением по имени и просмотрите его ещё раз. Обратите внимание на то, что значения вычислялись лишь при сопоставлении с образцом. Мы вычисляем верхний конструктор аргумента лишь для того, чтобы понять какое уравнение для foldNat выбрать. Теперь мы будем хранить ссылку на (add Zero two) в памяти и как только, внешняя функция запросит верхний конструктор мы обновим значение в памяти новым вычисленным до корневого конструктора значением. Если в любом другом месте функции мы вновь обратимся к значению, мы не будем его перевычислять, а сразу вернём конструктор. Посмотрим как это происходит на примере:
-- выражение | память:
--------------------------------------------|-------------------------
(\x -> add (add x x) x) M | M = (add Zero two)
-- подставим ссылку в тело функции |
=> add (add M M) M |
-- раскроем самый верхний синоним |
=> foldNat (add M M) Succ M |
-- для foldNat узнаем верхний конструктор |
-- последнего аргумента (пропуская |
-- промежуточные шаги, такие же как выше) |
=> | M = Succ M1
| M1 = foldNat Succ Zero one
-- по M выбираем второе уравнение |
=> Succ (foldNat (add M M) Succ M1) |
-- запросим следующий верхний конструктор: |
=> | M = Succ M1
| M1 = Succ M2
| M2 = foldNat Succ Zero zero
-- по M1 выбираем второе уравнение |
=> Succ (Succ (foldNat (add M M) Succ M2)) |
-- теперь для определения уравнения foldNat |
-- раскроем M2 |
=> | M = Succ M1
| M1 = Succ M2
| M2 = Zero
-- выбираем первое уравнение для foldNat: |
=> Succ (Succ (add M M)) |
-- раскрываем самый верхний синоним: |
=> Succ (Succ (foldNat M Succ M)) |
-- теперь, поскольку M уже вычислялось, в |
-- памяти уже записан верхний конструктор, |
-- мы знаем, что это Succ и выбираем второе |
-- уравнение: |
=> Succ (Succ (Succ (foldNat M Succ M1))) |
-- и M1 тоже уже вычислялось, сразу |
-- выбираем второе уравнение |----+
=> Succ (Succ (Succ (Succ (foldNat M Succ M2)))) |
-- M2 вычислено, идём на первое уравнение |----+
=> Succ (Succ (Succ (Succ (Succ M)))) |
-- далее остаётся только подставить уже |
-- вычисленные значения M |
-- и вернуть значение. |
Итак подставляется не значение а ссылка на него, вычисленная часть значения используется сразу в нескольких местах. Эта стратегия редукции называется вычислением по необходимости (call by need) или ленивой стратегией вычислений (lazy evaluation).
Теперь немного терминологии. Значение может находится в четырёх состояниях:
Нормальная форма (normal form, далее НФ), когда оно полностью вычислено (нет синонимов);
Слабая заголовочная НФ (weak head NF, далее СЗНФ), когда известен хотя бы один верхний конструктор;
Отложенное вычисление (thunk), когда известен лишь рецепт вычисления;
Дно (bottom, часто рисуют как $\bot$), когда известно, что значение не определено.
Вы могли понаблюдать за значением в первых трёх состояниях на примере выше. Но что такое $\bot$? Вспомним определение для функции извлечения головы списка head:
head :: [a] -> a head (a:_) = a head [] = error "error: empty list"
Второе уравнение возвращает $\bot$. У нас есть две функции, которые возвращают это “значение”:
undefined :: a error :: String -> a
Первая – это $\bot$ в чистом виде, а вторая не только возвращает неопределённое значение, но и приводит к выводу на экран сообщения об ошибке. Обратите внимание на тип этих функций, результат может быть значением любого типа. Это наблюдение приводит нас к ещё одной тонкости. Когда мы определяем тип:
data Bool = False | True data Maybe a = Nothing | Just a
На самом деле мы пишем:
data Bool = undefined | False | True data Maybe a = undefined | Nothing | Just a
Компилятор автоматически прибавляет ещё одно значение к любому определённому пользователем типу. Такие типы называют поднятыми (lifted type). А значения таких типов принято называть запакованными (boxed). Не запакованное (unboxed) значение – это простое примитивное значение. Например целое или действительное число в том виде, в котором оно хранится на компьютере. В Haskell даже числа “запакованы”. Поскольку нам необходимо, чтобы undefined могло возвращать в том числе и значение типа Int:
data Int = undefined | I# Int#
Тип Int# – это низкоуровневое представление ограниченного целого числа. Принято писать не запакованные типы с решёткой на конце. I# – это конструктор. Нам приходится запаковывать значения ещё и потому, что значение может принимать несколько состояний (в зависимости от того, насколько оно вычислено), всё это ведёт к тому, что у нас хранится не просто значение, а значение с какой-то дополнительной информацией, которая зависит от конкретной реализации языка Haskell.
Мы решили проблему дублирования вычислений, но наше решение усугубило проблему расхода памяти. Ведь теперь мы храним не просто значения, но ещё и дополнительную информацию, которая отвечает за проведение вычислений. Эта проблема может проявляться в очень простых задачах. Например попробуем вычислить сумму чисел от одного до миллиарда:
sum [1 .. 1e9] <interactive>: out of memory (requested 2097152 bytes)
Интуитивно кажется, что для решения этой задачи нам нужно лишь две ячейки памяти. В одной мы будем постоянно прибавлять к значению единицу, пока не дойдём до миллиарда, так мы последовательно будем получать элементы списка, а в другой мы будем хранить значение суммы. Мы начнём с нуля и будем прибавлять значения первой ячейки. У ленивой стратегии другое мнение на этот счёт. Если вы вернётесь к примеру выше, то заметите, что sum копит отложенные выражения до самого последнего момента. Поскольку память ограничена, такой момент не наступает. Как нам быть? В Haskell по умолчанию все вычисления проводятся по необходимости, но предусмотрены и средства для имитации вычисления по значению. Давайте посмотрим на них.
Языки с ленивой стратегией вычислений называют не строгими (non-strict), а языки с энергичной стратегией вычислений соответственно~– строгими.
Мы говорили о том, что при вычислении по имени значения вычисляются только при сопоставлении с образцом или в case-выражениях. Есть специальная функция seq, которая форсирует приведение к СЗНФ:
seq :: a -> b -> b
Она принимает два аргумента, при выполнении функции первый аргумент приводится к СЗНФ и затем возвращается второй. Вернёмся к примеру с sum. Привести к СЗНФ число – означает вычислить его полностью. Определим функцию sum', которая перед рекурсивным вызовом вычисляет промежуточный результат:
sum' :: Num a => [a] -> a
sum' = iter 0
where iter res [] = res
iter res (a:as) = let res' = res + a
in res' `seq` iter res' as
Сохраним результат в отдельном модуле 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 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':
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 не вычисляет свой первый аргумент полностью. Первый аргумент не приводится к нормальной форме. Мы лишь просим вычислитель узнать какой конструктор находится в корне у данного выражения. Например в выражении 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
division (sum, leng) = sum / fromIntegral leng
Такой вот монстр. Функция seq право ассоциативна поэтому скобки будут группироваться в нужном порядке. В этом определении мы просим вычислитель привести к СЗНФ числа, а не пары чисел, как в прошлой версии. Для чисел СЗНФ совпадает с НФ, и всё должно пройти гладко, но сохраним это определение и проверим результат:
Prelude Strict> :! ghc --make Strict [1 of 1] 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 фиксировано стандартом, но каждый разработчик компилятора может вносить свои дополнения. Они подключаются через директиву LANGUAGE:
{-# LANGUAGE
Расширение1,
Расширение2,
Расширение3 #-}
Мы заключаем директиву в специальные комментарии с решёткой, говорим LANGUAGE а затем через запятую перечисляем имена расширений, которые нам понадобятся. Расширения активны только в рамках данного модуля. Например если мы импортируем функции из модуля, в котором включены расширения, то эти расширения не распространяются дальше на другие модули. Такие комментарии с решёткой называют прагмами (pragma).
Нас интересует расширение BangPatterns (bang – восклицательный знак, вы сейчас поймёте почему оно так называется). Посмотрим на функцию, которая использует энергичные образцы:
iter (!sum, !leng) a = (step + a, leng + 1)
В декомпозиции пары перед переменными у нас появились восклицательные знаки. Они говорят вычислителю о том, чтобы он так уж и быть сделал ещё одно усилие и заглянул в корень значений переменных, которые были переданы в эту функцию.
Вычислитель говорит ладно-ладно сделаю. А там числа! И получается, что они не накапливаются. С помощью энергичных образцов мы можем переписать функцию mean' через foldl', а не выписывать её целиком:
mean'' :: [Double] -> Double
mean'' = division . foldl' iter (0, 0)
where iter (!sum, !leng) a = (sum + a, leng + 1)
division (sum, leng) = sum / fromIntegral leng
Проверим в интерпретаторе
*Strict> :! ghc --make Strict [1 of 1] Compiling Strict ( Strict.hs, Strict.o ) *Strict> :l Strict Ok, modules loaded: Strict. (0.00 secs, 581304 bytes) Prelude Strict> mean'' [1 .. 1e7] 5000000.5 (0.78 secs, 1412862488 bytes) Prelude Strict> mean' [1 .. 1e7] 5000000.5 (0.65 secs, 1082640204 bytes)
Функция работает чуть медленнее, чем исходная версия, но не сильно.
Расширение BangPatterns позволяет указывать какие значения привести к СЗНФ не только в образцах, но и в типах данных. Мы можем создать тип:
data P a b = P !a !b
Этот тип обозначает пару, элементы которой обязаны находиться в СЗНФ. Теперь мы можем написать ещё один вариант функции поиска среднего:
mean''' :: [Double] -> Double
mean''' = division . foldl' iter (P 0 0)
where iter (P sum leng) a = P (sum + a) (leng + 1)
division (P sum leng) = sum / fromIntegral leng
У вас может сложиться ошибочное представление, что ленивые вычисления созданы только для того, чтобы с ними бороться. Пока мы рассматривали лишь недостатки, вскользь упомянув о преимуществе выразительности. Ленивые вычисления могут и экономить память! Мы можем строить огромные промежуточные данные, обрабатывать их разными способами при условии, что в конце программы нам потребуется лишь часть этих данных или конечный алгоритм будет накапливать определённую статистику.
Рассмотрим такое выражение:
let longList = produce x in sum' $ filter p $ map f longList
Функция produce строит огромный список промежуточных данных. Далее мы преобразуем эти данные функцией f и фильтруем их предикатом p. Всё это делается для того, чтобы посчитать сумму всех элементов в списке. Посмотрим как повела бы себя в такой ситуации энергичная стратегия вычислений. Сначала был бы вычислен список longList, причём полностью. Затем все элементы были бы преобразованы функцией f. У нас в памяти уже два огромных списка. Теперь мы фильтруем весь список и в самом конце суммируем. Было бы очень плохо заставлять энергичный вычислитель редуцировать такое выражение.
А в это время ленивый вычислитель поступит так. Сначала всё выражение будет сохранено в виде описания, затем он скажет разверну сначала sum', эта функция запросит первый элемент списка, что приведёт к вызову filter. Фильтр будет запрашивать следующий элемент списка у подчинённых ему функций до тех пор, пока предикат p не вернёт True на одном из них. Всё это время функция map будет вытягивать из produce по одному элементу. Причём память, выделенная на промежуточные не нужные значения (на них p вернул False) будет переиспользована. Как только sum' прибавит первый элемент, она запросит следующий, проснётся фильтр и так далее. Вся функция будет работать в постоянном ограниченном объёме памяти, который не зависит от величины списка longList!
Примерам ленивых вычислений будет посвящена отдельная глава, а пока приведём один пример. Найдём корень уравнения с помощью метода неподвижной точки. У нас есть функция f :: a -> a, и нам нужно найти решение уравнения:
f x = x
Можно начать с какого-нибудь стартового значения, и подставлять, подставлять, подставлять его в f до тех пор, пока значение не перестанет изменяться. Так мы найдём решение.
x1 = f x0 x2 = f x1 x3 = f x2 ... до тех пор пока abs (x[N] - x[N-1]) <= eps
Первое наблюдение: функция принимает не произвольные значения, а те для которых имеет смысл операции: минус, поиск абсолютного значения и сравнение на больше/меньше. Тип нашей функции:
f :: (Ord a, Num a) => a -> a
Ленивые вычисления позволяют нам отделить шаг генерации решений, от шага проверки сходимости. Сначала мы сделаем список всех подстановок функции f, а затем найдём в этом списке два соседних элемента расстояние между которыми достаточно мало. Итак первый шаг, генерируем всю последовательность:
xNs = iterate f x0
Мы воспользовались стандартной функцией iterate из Prelude. Теперь ищем два соседних числа:
converge :: (Ord a, Num a) => a -> [a] -> a
converge eps (a:b:xs)
| abs (a - b) <= eps = a
| otherwise = converge eps (b:xs)
Поскольку список бесконечный мы можем не проверять случаи для пустого списка. Итоговое решение:
roots :: (Ord a, Num a) => a -> a -> (a -> a) -> a roots eps x0 f = converge eps $ iterate f x0
За счёт ленивых вычислений функции converge и iterate работают синхронно. Функция converge запрашивает новое значение и iterate передаёт его, но только одно! Найдём решение какого-нибудь уравнения. Запустим интерпретатор. Мы ленимся и не создаём новый модуль для такой “большой” функции. Определяем её сразу в интерпретаторе.
Prelude> let converge eps (a:b:xs) = if abs (a-b)<=eps then a else converge eps (b:xs) Prelude> let roots eps x0 f = converge eps $ iterate f x0
Найдём корень уравнения:
$$x (x-2) = 0$$
$$x^2 - 2 x = 0$$
$$\frac{1}{2} x^2 = x$$
Prelude> roots 0.001 5 (\x -> x*x/2)
Метод завис, остаётся только нажать ctrl+c для остановки. На самом деле есть одно условие для сходимости метода. Метод сойдётся, если модуль производной функции f меньше единицы. Иначе есть возможность, что мы будем бесконечно генерировать новые подстановки. Вычислим производную нашей функции:
$$\frac{d}{dx} \frac{1}{2} x^2 = x$$
Нам следует ожидать решения в интервале от минус единицы до единицы:
Prelude> roots 0.001 0.5 (\x -> x*x/2) 3.0517578125e-5
Мы нашли решение, корень равен нулю. В этой записи Ne-5 означает $N \cdot 10^{-5}$
В этой главе мы узнали о том как происходят вычисления в Haskell. Мы узнали, что они ленивые. Всё вычисляется как можно позже и как можно меньше. Такие вычисления называются вычислениями по необходимости.
Также мы узнали о вычислениях по значению и вычислениях по имени.
В вычислениях по значению редукция проводится от листьев дерева выражения к корню
В вычислениях по имени редукция проводится от корня дерева выражения к листьям.
Вычисление по необходимости является улучшением вычисления по имени. Мы не дублируем выражения во время применения. Мы сохраняем значения в памяти и подставляем в функцию ссылки на значения. После вычисления значения происходит его обновление в памяти. Так если в одном месте выражение уже было вычислено и мы обратимся к нему по ссылке из другого места, то мы не будем перевычислять его, а просто считаем готовое значение.
Мы познакомились с терминологией процесса вычислений. Выражение может находится в нормальной форме. Это значит что оно вычислено. Может находится в слабой заголовочной нормальной форме. Это значит, что мы знаем хотя бы один конструктор в корне выражения. Также возможно выражение ещё не вычислялось, тогда оно является отложенным (thunk).
Суть ленивых вычислений заключается в том, что они происходят синхронно. Если у нас есть композиция двух функций:
$$g\ (f\ x)$$
Внутренняя функция f не начнёт вычисления до тех пор пока значения не понадобятся внешней функции g. О последствиях этого мы остановимся подробнее в отдельной главе. Значения могут потребоваться только при сопоставлении с образцом. Когда мы хотим узнать какое из уравнений нам выбрать.
Иногда ленивые вычисления не эффективны по расходу памяти. Это происходит когда выражение состоит из большого числа подвыражений, которые будут вычислены в любом случае. В Haskell у нас есть способы борьбы с ленью. Это функция seq, энергичные образцы и энергичные типы данных.
Функция seq:
seq :: a -> b -> b
Сначала приводит к слабой заголовочной форме свой первый аргумент, а затем возвращает второй. Взрывные образцы выполняют те же функции, но они используются в декомпозиции аргументов или в объявлении типа.
Потренируйтесь в понимании того как происходят ленивые вычисления. Вычислите на бумаге следующие выражения (если это возможно):
sum $ take 3 $ filter (odd . fst) $ zip [1 ..] [1, undefined, 2, undefined, 3, undefined, undefined]
take 2 $ foldr (+) 0 $ map Succ $ repeat Zerotake 2 $ foldl (+) 0 $ map Succ $ repeat Zero
Функция seq приводит первый аргумент к СЗНФ, убедитесь в этом на таком эксперименте. Определите тип:
data TheDouble = TheDouble { runTheDouble :: Double }
Он запаковывает действительные числа в конструктор. Определите для этого типа экземпляр класса Num и посмотрите как быстро будет работать функция sum' на таких числах. Как изменится скорость если мы заменим в определении типа data на newtype? как изменится скорость, если мы вернём data, но сделаем тип TheDouble энергичным? Поэкспериментируйте.
Посмотрите на приведение к СЗНФ в энергичных типах данных. Определите два типа:
data Strict a = Strict !a data Lazy a = Lazy a
И повычисляйте в интерпретаторе различные значения с undefined, const, ($!) и seq:
> seq (Lazy undefined) "Hi" > seq (Strict undefined) "Hi" > seq (Lazy (Strict undefined)) "Hi" > seq (Strict (Strict (Strict undefined))) "Hi"
Посмотрите на такую функцию вычисления суммы всех чётных и нечётных чисел в списке.
sum2 :: [Int] -> (Int, Int)
sum2 = iter (0, 0)
where iter c [] = c
iter c (x:xs) = iter (tick x c) xs
tick :: Int -> (Int, Int) -> (Int, Int)
tick x (c0, c1) | even x = (c0, c1 + 1)
| otherwise = (c0 + 1, c1)
Эта функция очень медленная. Кто-то слишком много ленится. Узнайте кто, и ускорьте функцию.