вычислений. Или посмотрим на такое совсем простое свойство:
map id = id
Если мы заменим левую часть на правую, то число сэкономленных усилий будет пропорционально длине
списка. Вряд ли программист станет писать такие выражения, однако они могут появиться после выполнения
других оптимизаций, например после многих встраиваний различных функций.
Можно представить, что эти правила являются дополнительными уравнениями в определении функции:
map f []
= []
map f (x:xs)
= f x : map f xs
map id a
= a
map f (map g x) = map (f . g) x
Словно теперь мы можем проводить сопоставление с образцом не только по конструкторам, но и по выра-
жениям самого языка и функция map стала конструктором. Что интересно, зависимости могут быть какими
угодно, они могут выражать закономерности, присущие той области, которую мы описываем. В дополни-
тельных уравнениях мы подставляем аргументы так же как и в обычных, если где-нибудь в коде программы
находится соответствие с левой частью уравнения, мы заменяем её на правую. При этом мы пишем правила
так, чтобы действительно происходила оптимизация программы, поэтому слева пишется медленная версия.
Такие дополнительные правила пишутся в специальной прагме RULES:
{-# RULES
”map/compose”
forall f g x.
map f (map g x)
= map (f . g) x
”map/id”
map id
= id
#-}
Первым в кавычках идёт имя правила. Оно используется только для подсчёта статистики (например ес-
ли мы хотим узнать сколько правил сработало в данном прогоне программы). За именем правила пишут
уравнение. В одной прагме может быть несколько уравнений. Правила разделяются точкой с запятой или
переходом на другу строку. Все свободные переменные правила перечисляются в окружении forall (... )
. ~. Компилятор доверяет нам абсолютно. Производится только проверка типов. Никаких других проверок не
проводится. Выполняется ли на самом деле это свойство, будет ли вычисление правой части действительно
проще программы вычисления левой – известно только нам.
Отметим то, что прагма RULES применяется до тех пор пока есть возможность её применять, при этом мы
можем войти в бесконечный цикл:
{-# RULES
”infinite”
forall a b. f a b = f b a
#-}
С помощью прагмы RULES можно реализовать очень сложные схемы оптимизации. Так в Prelude реализу-
ется слияние (fusion) списков. За счёт этой оптимизации многие выражения вида свёртка/развёртка не будут
производить промежуточных списков. Этой схеме будет посвящена отдельная глава. Например если список
преобразуется серией функций map, filter и foldr промежуточные списки не строятся.
Посмотрим как работает прагма RULES, попробуем скомпилировать такой код:
module Main where
data List a = Nil | Cons a (List a)