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

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

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

К образцам предъявляется одноединственое требование, котороебез должно выполняться беспрекословно, иначекоторого сопоставление с образцами будетможет быть выполнено неверно. Требование это звучит следующим образом: при сопоставлении образца с данными означивание переменных должно происходить единственным образом. Т.&nbsp;е., например, выражение <math>(1 + X \Rightarrow 5)</math> можно использовать как образец, т.&nbsp;к. означивание переменной <math>X</math> происходит единственным образом (<math>X = 4</math>), а выражение <math>(X + Y \Rightarrow 5)</math> использовать в качестве образца нельзя, ибо означить переменные <math>X</math> и <math>Y</math> можно различным образом.

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

#*<math>Set</math> — функция, возвращающая список из всех атомов, содержащийсодержащихся единичныев вхождениязаданном атомовсписке. Каждый атом должен присутствовать в результирующем списке в заданногоединственном спискачисле.