Основы функционального программирования/Структуры данных и базисные операции — 2

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

Типы в функциональных языках [ править ]

В первой лекции говорилось, что аргументами функций могут быть не только переменные базовых типов, но и другие функции. В этом случае появляется понятие функций высшего порядка. Но для рассмотрения функций высшего порядка необходимо ввести понятие функционального типа (или тип функции). Пусть некоторая функция f — это функция одной переменной из множества A , принимающая значение из множества B . Тогда по определению:

Соответственно выражение, в котором все функции рассматриваются как функции одного аргумента, а единственной операцией является аппликация (применение), называются выражениями в форме «оператор-операнд». Такие функции получили название «каррированные», а сам процесс сведения типа функции к виду, приведённому в предыдущем абзаце — каррированием (по имени Карри Хаскелла).

В λ-исчислении также присутствует математическая абстракция для аппликативных форм записей. Например:

Несколько слов о нотации абстрактного языка [ править ]

Необходимо отметить, что в нотации абстрактного функционального языка, который использовался до сих пор для написания примеров функций, можно было бы использовать такую конструкцию, как if − then − else . Например, при описании функции append (см. пример 7), её тело можно было бы записать следующим образом:

append ⁡ ( L 1 , L 2 ) = if ⁡ ( L 1 = [ ] )   then ⁡   L 2   else ⁡   head ⁡ ( L 1 ) : append ⁡ ( tail ⁡ ( L 1 ) , L 2 )

Однако данная запись чревата непониманием и трудным разбором. Поэтому даже в примере 7 была использована нотация, которая поддерживает так называемые «образцы».

Определение:

Образцом называется выражение, построенное с помощью операций конструирования данных, которое используется для сопоставления с данными. Переменные обозначаются прописными буквами, константы — строчными.

Кроме образцов в функциональном программировании вводится такое понятие, как «клоз» (от англ. «clause»). По определению клозы выглядят так:

Таким образом, определение функции в функциональном программировании есть просто последовательность клозов (возможно состоящая из одного элемента). Для того, чтобы упростить запись определений функций, далее слово d e f будет опускаться.

Интерпретация вызова функции заключается в нахождении первого по порядку сверху вниз образца, успешно сопоставимого с фактическим параметром. Значение переменных образца, означиваемые в результате сопоставления, подставляются в правую часть клоза (выражение expr ), вычисленное значение которой в данном контексте объявляется значением вызова функции.

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

Представленная запись не очень читабельна, поэтому использоваться она будет только в крайних случаях по необходимости.

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

Элементы программирования [ править ]

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

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

Чтобы ответить на данный вопрос положительно, необходимо рассмотреть понятие аккумулятора (накопителя). Для этого можно рассмотреть следующий пример:

Пример 10. Функция вычисления факториала с аккумулятором.

F ( N , A ) = F ( ( N − 1 ) , ( N ⋅ A ) )

Хвостовая рекурсия представляет собой специальный вид рекурсии, в которой имеется единственный вызов рекурсивной функции и при этом этот вызов выполняется после всех вычислений.

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

1. Вводится новая функция с дополнительным аргументом (аккумулятором), в котором накапливаются результаты вычислений.
2. Начальное значение аккумулирующего аргумента задается в равенстве, связывающем старую и новую функции.
3. Те равенства исходной функции, которые соответствуют выходу из рекурсии, заменяются возвращением аккумулятора.
4. Равенства, соответствующие рекурсивному определению, выглядят как обращения к новой функции, в котором аккумулятор получает то значение, которое возвращается исходной функцией.

Возникает вопрос: любую ли функцию можно преобразовать для вычисления с аккумулятором? Очевидно, что ответ на этот вопрос отрицателен. Построение функций с накапливающим параметром — приём не универсальный, и он не гарантирует получения хвостовой рекурсии. С другой стороны, построение определений с накапливающим параметром является делом творческим. В этом процессе необходимы некоторые эвристики.

Определение:

Общий вид рекурсивных определений, позволяющих при трансляции обеспечить вычисления в постоянном объёме памяти через итерацию, называется равенствами в итеративной форме.

Общий вид равенств в итеративной форме может быть описан следующим образом: