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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Определение функции
foldr
может быть выведено с помощью параметризации
определения функции
sum:
(foldr f x) [] = x
(foldr f x) (h : t) = f h ((foldr f x) t)
Мы пишем скобки
(foldr f x)
, чтобы было понятнее, на что заменено выражение
sum
.
Удобно скобки опускать и поэтому ((foldr f x) t) может быть переписано как
(foldr f x t)
. Отметим следующий факт: функция от трех аргументов, такая как
foldr,
может использоваться только с двумя аргументами, возвращая в качестве результата
функцию от одного остающегося аргумента. Так вызов foldr (+) 0
возвращает функ-
цию
sum
от одного аргумента – списка.
Проведенная модуляризация функции
sum
подсказывает использовать ее части в
других ситуациях. Наиболее интересная часть есть
foldr
, которую мы теперь можем ис-
пользовать для нахождения произведения всех элементов списка без программирования:
product = foldr (*) 1
Точно таким же образом, мы можем написать логические функции для списка булевских
значений
and, or :: [Bool] -> Bool
and = foldr (&&) True
or = foldr (||) False
Один из способов понимать foldr f x
– считать это функцией, которая заменяет
все символы «
:
» в списке символом
f
, и все вхождения пустого списка
[]
символом
x
. Ес-
ли взять список
[1,2,3]
в качестве примера, то его можно переписать в виде
(:) 1 ((:) 2 ((:) 3 []))
и функция (foldr (+) 0)
конвертирует это выражение в выражение
(+) 1 ((+) 2 ((+) 3 0))
и (foldr (*) 1)
преобразует это выражение в соответствующее выражение
(*) 1 ((*) 2 ((*) 3 1))
Очевидно, что (
foldr (:) [])
просто копирует список. Конкатенацию (соединение) двух
списков мы можем определить как
append a b = foldr (:) b a
Пример:
append [1,2] [3,4]
⇒ foldr (:) [3,4] [1,2]
⇒ (foldr (:) [3,4]) ((:) 1 ((:) 2 []))
(заменили (:)на (:)и []на [3,4])
⇒ (:) 1 ((:) 2 [3,4])
⇒ [1,2,3,4]
Декомпозируя простую функцию (sum
) как комбинацию «функции высокого по-
рядка» и некоторого простого аргумента, мы пришли к такой функции (foldr
), которая
может быть использована для определения многих функций для списков без больших
76

Страницы