Специальная математика. Соловьев А.Е. - 97 стр.

Первым языком функционального программирования был язык LISP и многие базовые
понятия этого языка стали классикой функционального программирования.

 Базовые функции функционального программирования:
car(x) - дает первый элемент списка х ;
cdr(х) - хвост списка ( список без первого элемента) ;
cons(x,y) - добавляет элемент х к списку у;
append(x,y) - добавляет список y к списку x ;

Примеры.
Пусть x = (1, 2, 3) y = (4, 5)
car(x) = (1);
cdr(х) = (2, 3);
cons(x,y) = ((1, 2, 3), 4, 5);
append(x,y) = (1, 2, 3, 4, 5).

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


Примеры.
Функция дл вычисления длины списка

дл(х)  if(x) = nil then 0 else дл(cdr(x)) + 1

Вычислим функцию для конкретного списка.
дл(A, B, C) = дл(B, C) + 1
дл(B, C) = дл(C) + 1
дл(C) = дл(nil) + 1
дл (nil) = 0
"Пройдя" в обратном направлении можно получить числовое значение.

Обращение списка обр, то есть список A, B, C обратится в список C, B, A

 обр(x, y)  if x = nil then y else обр(cdr(x), cons(car(x), y))

Вычислим функцию для конкретного списка
обр(A, B, C, nil) = обр((B, C), (A))
обр((B, C), (A)) = обр((C), (B, A))
обр((C), (B, A)) = обр((nil), C, B, A)

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


Функциональный язык Бэкуса.
 LISP, созданный в начале 60-х годов, не единственный функциональный язык, хотя и самый
распространенный.
Интересный функциональный язык РЕФАЛ был разработан в 70-х годах нашим
соотечественником Турчиным и исподльзовал математическую модель нормальных
алгорифмов Маркова.

                                                 — 97 —