Функциональное программирование

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

Рассмотрим, как можно определить функцию для нахождения длины списка. Длина пустого списка равна 0. При удалении первого элемента список становится короче на один элемент.

Для часто используемого сравнения с пустым списком можно определить функцию `"null"(x)="eq"(x,'())`. Поиск элемента в списке можно определить следующим образом. Если список пуст, то заданного элемента в списке нет, возвращаем ложь (т.е. #F). Если заданный элемент совпадает с первым элементом списка, то возвращаем истину (т.е. #T), иначе выполняем поиск в оставшейся части списка.

Часто бывает полезной функция для соединения двух списков.

Функцию реверсирования списка легко написать, используя функцию cоединить.

Здесь cons(car(x), '()) используется для создания списка из одного элемента. Но эта реализация не является эффективной. Ускорить работу функции можно, используя дополнительный параметр, в котором накапливается результат для обработанной час-ти списка. В случае реверсирования списка, первый элемент из необработанной части списка должен стать первым элементом в промежуточном результате.

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

Это определение соответствует следующему циклу:

struct item { 
  int val; 
  struct item *next;
} *x;
int s=0; int p=1;
while(x!=NULL)
{ s=s+x->val; p=p*x->val; x=x->next;
}

Иногда в определении функции встречаются одинаковые подвыражения. Удобно дать этих подвыражениям какое-либо имя, уменьшая таким образом сложность определения функции. Для этого используются блоки локальных определений `{bb"пусть"\ x_1=e_1;\ x_2=e_2;\ …;\ x_k=e_k\ в\ e`} и `{e\ bb"где"\ x_1=e_1;\ x_2=e_2;\ …;\ x_k=e_k}`, где `x_1,\ x_2,\ …,\ x_k` – имена для значений выражений `e_1,\ e_2,\ …,\ e_k`, a `e` – выражение, в котором используются эти именованные значения. Результатом вычисления блока локальных определений является значение выражения `e`. Например, функцию `"суммпроиз"` можно определить, не используя вспомогательную функцию `"сп"`:

1. Определите функцию `"вставить"(x,s)`, вставляющую число `x` в упорядоченный числовой список `s`. Используйте эту функцию для определения функции сортировки вставками.

2. Определите функцию `"элемент"(i,s)`, возвращающую `i`-й элемент списка `s`.

3. Определите функцию `"подсписок"(s,n,m)`, выделяющую подсписок из списка `s`, начиная с `n`-го элемента, длиной `m`.

4. Определите функцию `"колмин"(s)`, возвращающую список из минимального значения списка `s` и количества элементов, равных минимальному. Например, результатом вызова `"колмин"`('(2 1 5 7 1 5 1)) является список (1 3).

5. Определите функцию `"пополам"(s)`, возвращающую список из двух списков. В первый список должны попасть элементы, стоящие на нечетных позициях списка s, во второй список – на четных. Например, вызов `"пополам"`('(A B C D E)) должен вернуть список ((A C E) (B D)).

6. Определите функции для определения пересечения и объединения двух множеств, заданных в виде списков.

7. Определите функцию `"упоряд"(s)`, возвращающую #T, если числовой список s является упорядоченным по возрастанию, и #F в противном случае.

8. Определите функцию `"линеар"(s)` для линеаризации списка s. Например, вызов `"линеар"`(‘((A B) (C (D)))) должен вернуть список (A B C D)

9. Определите функцию `"подмножество"(a,b)`, определяющую, является ли множество `a` подмножеством множества `b`.

10. Определите функцию `"подстрока"(a,b)`, определяющую, содержится ли последовательность `a` (в указанном порядке, целиком и непрерывно) `в` последовательности `b`.

11. Определите функцию `"слияние"(a,b)`, объединяющую два упорядоченных по возрастанию числовых списка `a` и `b` в новый упорядоченный список. Используйте функции `"слияние"` и `"пополам"` для определения функции сортировки числового списка.