Математическое введение в декларативное программирование. Зюзысов В.М. - 75 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Используя карринг, функция от n аргументов может быть рассмотрена как функция
от одного аргумента, которая возвращает функцию от n-1 аргументов.
Функция подобная
f x y z = sq x * sq y * sq z where
sq v = v * v
что требует три целых аргумента и возвращает целый результат, имеет тип
Int -> Int -> Int -> Int
Однако это не означает, что такая функция должна всегда появляться точно с тремя аргу-
ментами в выражении. Вместо этого функция может появиться с любым меньшим коли-
чеством аргументов и в этом случае она рассматривается как анонимная функция (функ-
ция без имени), которую в свою очередь можно применить к недостающим аргументам.
Это означает, что (
f 7)
есть правильное выражение типа
Int -> Int -> Int
, и
(f 7 13)
обозначает функцию типа
Int -> Int
. Заметим, что синтаксический разбор выражения
подобного f 7 13 0
дает ((
f 7) 13) 0
. И поэтому выражение для типа
Int -> Int ->
Int -> Int
анализируется как
Int -> (Int -> (Int -> Int))
.
Использование функций высших порядков позволяет достигать высокой абстрак-
ции и создавать «универсальные» функции. Одной из такой функции является foldr
.
Рассмотрим задачи со списками целых чисел. Определим рекурсивную функцию
sum
, возвращающую сумму элементов списка. Функция должна быть определена для двух
видов аргумента: пустого списка и списка, содержащего элементы. Так как сумма пустого
множества чисел, очевидно, ноль, то мы определяем:
sum [] = 0
В общем случае чтобы вычислить сумму элементов списка x : xs
, мы вычисляем сумму
хвоста списка – подсписка, начинающего со второго элемента, – и прибавляем значение
первого элемента:
sum (x : xs) = x + sum xs
Изучая это определение, мы обнаруживаем, что только его части, ограниченные
рамками, связаны именно с вычислением суммы.
+---+
sum [] = | 0 |
+---+
+---+
sum (x : xs) = x | + | sum xs
+---+
Это означает, что вычисление суммы может быть модуляризовано с помощью «склеива-
ния» вместе общего рекурсивного образца и частей, ограниченных прямоугольниками.
Этот рекурсивный образец называется
foldr
и функция
sum
может быть записана в виде
sum = foldr (+) 0
где операторное обозначение суммы заменено функциональным обозначением:
(+) x y = x + y
75

Страницы