Теоретический минимум по Computer Science

Функциональное программирование. В парадигме функционального программирования функции — это больше, чем просто процедуры. Они используются для объявления связи между двумя или более элементами, почти как математические уравнения. В функциональной парадигме первоклассными объектами являются функции. Они обрабатываются так же, как любой другой примитивный тип данных, например строки и числа.

Функции могут получать другие функции в аргументах и возвращать функции в виде результата. Функции, имеющие такие признаки, называются функциями высшего порядка. Многие основные языки программирования включают такие элементы из функциональной парадигмы. Вам следует непременно воспользоваться их выразительностью при первой возможности.

Например, большинство языков функционального программирования поставляются вместе с универсальной функцией sort. Она может сортировать любую последовательность элементов. Функция sort на входе принимает другую функцию, которая определяет, как элементы будут сравниваться в процессе сортировки. Например, переменная coordinates содержит список географических точек. При наличии двух точек функция closer_to_home сообщает, какая из них находится ближе к вашему дому. Вы можете отсортировать список точек по критерию близости к вашему дому, как это сделано тут:

sort(coordinates, closer_to_home)

Функции высшего порядка часто используются для фильтрации данных. Языки функционального программирования также предлагают универсальную функцию filter, получающую набор элементов, и функцию, которая указывает, следует ли отбросить заданный элемент или нет. Например, удаление четных чисел из списка можно записать так:

odd_numbers ← filter(numbers, number_is_odd)

number_is_odd — это функция, которая получает число и возвращает True, если число является нечетным, и False в противном случае.

Еще одна типичная задача, которая возникает во время программирования, — применение специальной функции ко всем элементам в списке. В функциональном программировании она называется отображением. Многие языки имеют встроенную функцию map, предназначенную для этой задачи. Например, вычисление квадрата каждого числа в списке можно организовать так:

squared_numbers ← map(numbers, square)

Функция square возвращает квадрат заданного числа. Операции отображения и фильтрации встречаются так часто, что многие языки программирования предлагают возможность записи этих выражений в более простой форме. Например, в языке программирования Python вычислить квадраты чисел в списке можно так:

squared_numbers = [x**2 for x in numbers]

Эта форма записи называется «синтаксическим сахаром»: дополнительной синтаксической конструкцией, позволяющей записывать выражения короче и понятнее. Многие языки программирования предоставляют несколько форм «синтаксического сахара». Применяйте их и злоупотребляйте ими.

Наконец, когда нужно обработать список значений так, чтобы свести процесс к единственному результату, вы можете воспользоваться функцией reduce. На входе она получает список, начальное значение и редуцирующую функцию. Начальное значение инициирует «аккумуляторную» переменную, которая будет обновляться редуцирующей функцией для каждого элемента в списке, а в конце — возвращена:

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 подсчитывает количество элементов в списке.

Функции высшего порядка могут не только принимать функции на входе, но также порождать и возвращать новые функции. Они даже в состоянии замкнуть ссылку на значение в сгенерированную функцию. Мы называем это замыканием. Функция, имеющая замыкание, «помнит» окружение, в котором была создана, и может обращаться к заключенным в нем значениям.