function reduce(list, initial_val, func)
····accumulator ← initial_val
····for item in list
········accumulator ← func(accumulator, item)
····return accumulator
Например, с помощью reduce можно просуммировать элементы в списке:
sum ← function(a, b): a + b
summed_numbers ← reduce(numbers, 0, sum)
Использование функции reduce упростит ваш программный код и сделает его более читаемым. Еще пример: если sentences — это просто список предложений, и вы хотите подсчитать общее количество слов в них, это можно реализовать так:
wsum ← function(a, b): a + length(split(b))
number_of_words ← reduce(sentences, 0, wsum)
Функция split разбивает строку на список слов, а функция length подсчитывает количество элементов в списке.
Функции высшего порядка могут не только принимать функции на входе, но также порождать и возвращать новые функции. Они даже в состоянии замкнуть ссылку на значение в сгенерированную функцию. Мы называем это замыканием. Функция, имеющая замыкание, «помнит» окружение, в котором была создана, и может обращаться к заключенным в нем значениям.
Используя замыкания, можно разбить исполнение функции, принимающей множество аргументов, на несколько шагов. Это называется каррингом. Предположим, что ваш программный код имеет такую функцию sum:
sum ← function(a, b): a + b
Функция sum ожидает два параметра, но ее можно вызвать с одним аргументом. Выражение sum(3) вернет не число, а новую каррированную функцию. При обращении к ней она вызовет sum и передаст ей 3 в первом аргументе. Ссылка на значение 3 замыкается в каррированной функции. Например:
sum_three ← sum(3)
print sum_three(1) # печатает "4".
special_sum ← sum(get_number())
print special_sum(1) # печатает "get_number() + 1".
Обратите внимание, что get_number не будет вызвана при создании функции special_sum. Вместо этого в определение special_sum будет заключена ссылка на get_number. Функция get_number вызывается только при вызове функции special_sum. Такой подход называется ленивыми, или отложенными, вычислениями, это очень важная особенность языков функционального программирования.
Замыкания также используются для генерации набора связанных функций, соответствующих шаблону. Использование шаблона функции поможет сделать код более читаемым и избежать дублирования. Давайте посмотрим на пример:
function power_generator(base)
····function power(x)
········return power(x, base)
····return power
Мы можем использовать power_generator для генерации разных функций, которые вычисляют степень:
square ← power_generator(2)
print square(2)····# печатает 4.
cube ← power_generator(3)
print cube(2)······# печатает 8.
Обратите внимание, что возвращаемые функции square и cube сохраняют значение переменной base. Она существовала только в среде power_generator, но несмотря на это возвращаемые функции абсолютно независимы от power_generator. Еще раз: замыкание — это функция, которая имеет доступ к некоторым переменным за пределами собственного контекста.
Еще замыкания можно использовать для управления внутренним состоянием функции. Давайте предположим, что вам нужна функция, которая накапливает сумму всех переданных ей чисел. Для этого можно использовать глобальную переменную:
GLOBAL_COUNT ← 0
function add(x)
····GLOBAL_COUNT ← GLOBAL_COUNT + x
····return GLOBAL_COUNT
Как вы уже знаете, глобальных переменных следует избегать, потому что они загрязняют пространство имен программы. Более чистый подход состоит в использовании замыкания, включающего ссылку на аккумуляторную переменную:
function make_adder()
····n ← 0
····function adder(x)
········n ← x + n
········return n
····return adder
Это позволит нам создать несколько сумматоров, не используя глобальные переменные:
my_adder ← make_adder()
print my_adder(5)·····# печатает 5.
print my_adder(2)·····# печатает 7 (5 + 2).
print my_adder(3)·····# печатает 10 (5 + 2 + 3).
Сопоставление с шаблоном. Функциональное программирование позволяет рассматривать функции как математические. При помощи математики мы можем описывать поведение функций в зависимости от входных данных. Обратите внимание на входной шаблон функции факториала:
0! = 1
n! = (n — 1)!
Функциональное программирование допускает сопоставление с шаблоном — то есть процесс распознавания этого шаблона. Вы можете просто написать:
factorial(0): 1
factorial(n): n × factorial(n — 1)
А вот императивное программирование требует, чтобы вы написали:
function factorial(n)
····if n = 0
········return 1
····else
········return n × factorial(n — 1)
Какая версия выглядит яснее? Я бы сделал выбор в пользу функциональной версии везде, где это возможно. Некоторые языки программирования строго функциональны; весь код на них эквивалентен чистым математическим функциям. Такие языки заходят настолько далеко, что являются вневременными, причем порядок инструкций в коде не влияет на его поведение. В таких языках все присвоенные переменным значения являются неизменяемыми. Мы называем это однократным присвоением. Поскольку состояние программы отсутствует, то и нет момента времени, когда переменная может измениться. Вычисления в строгой функциональной парадигме просто сводятся к вычислению функций и сопоставлению с шаблоном.
Логическое программирование
Всегда, когда вашей задачей является решение ряда логических формул, вы можете воспользоваться логическим программированием. Разработчик перечисляет логические высказывания о ситуации, например такие, как в разделе «Логика» главы 1. Затем выполняются запросы, чтобы получить ответы из предоставленной модели. Компьютер отвечает за интерпретацию логических переменных и запросов. Он также создает пространство решений из высказываний и занимается поиском ответов на запросы, которые удовлетворяют всем этим высказываниям.
