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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

усилий программирования. Все стандартные функции со списками можно реализовать с
помощью функции
foldr
. Нетрудно определить тип функции в общем случае:
foldr :: (a -> b -> b) -> b -> [a] -> b
Приведем ряд примеров использования функции foldr
. Функцию, которая удваи-
вает все элементы списка, можно определить так:
doubleall = foldr ((:) . double) []
where double n = 2*n
Функция map
применяет функцию
f
ко всем элементам списка. Эта функция является дру-
гим примером общей и полезнейшей функции в функциональном программировании.
map f = foldr ((:) . f) []
Обращение списка (переписывание элементов списка в противоположном порядке):
reverse = foldr postfix []
where postfix a x = x ++ [a]
Функция
filter
выбирает из списка только те элементы, которые удовлетворяют данно-
му предикату:
filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr f []
where f x xs | p x = x:xs
| otherwise = xs
Количество элементов в списке:
length :: [a] -> Int
length = foldr (\x, n -> 1+n) 0
Все эти возможности могут быть получены, потому что индивидуальные функции
в привычных императивных языках могут быть представлены в функциональном языке
как комбинация общей функции высокого порядка и некоторой частной специализиро-
ванной функции. Действия, которые мы проделывали, чтобы выделить функцию высокого
порядка называются абстракция вычислений. Мы обобщаем функции, имеющих одинако-
вый вид, т. е. определения этих функций с точки зрения абстракции вычислений сходны
по строению, но которые довольно различны с точки зрения производимых действий.
Однажды определенная такая функция высокого порядка позволяет очень легко за-
программировать многие различные действия. Как только вводится новый тип данных по-
лезно сразу определить соответствующую общую функцию (подобную
foldr
) для мани-
пулирования с новым типом данных. Тем самым обрабатывать данные становится
достаточно просто, и также локализуется знание о представлении данных нового типа.
Кроме того, функции высокого порядка позволяют избавиться от явной рекурсии.
Пример полезности функций высокого порядка. В 1979 году программист Richard
Waters изучал Fortran Scientific Subroutine Library, которая представляет собой важнейший
пакет, состоящий из тысяч строк кода, и широко использующий в то время. Он обнару-
жил, что если Fortran имел бы в своем составе три основные функции высокого порядка:
map, filter и foldr, то около 60% кода можно было переписать как вызовы этих функ-
ций. В этом случае значительно уменьшился бы объем библиотеки, и это также означает,
что повышение быстродействия пакета во многом зависело бы от оптимизации данных
функций.
77

Страницы