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

Стилистика
м
(Стилистика)
== Типы в функциональных языках ==
 
КакВ известнопервой лекции говорилось, что аргументами функций могут быть не только переменные базовых типов, но и другие функции. В этом случае появляется понятие функций высшего порядка. Но для рассмотрения функций высшего порядка необходимо ввести понятие функционального типа (или тип функции). Пусть некоторая функция <math>f</math> — это функция одной переменной из множества <math>A</math>, принимающая значение из множества <math>B</math>. Тогда по определению:
 
<center><math>\#(f) : A \rightarrow B</math></center>
Соответственно выражение, в котором все функции рассматриваются как функции одного аргумента, а единственной операцией является аппликация (применение), называются выражениями в форме «оператор-операнд». Такие функции получили название «каррированные», а сам процесс сведения типа функции к виду, приведённому в предыдущем абзаце — каррированием (по имени Карри Хаскелла).
 
Если вспомнитьВ λ-исчисление, то обнаружится, что в нёмисчислении уже́также естьприсутствует математическая абстракция для аппликативных форм записей. Например:
 
<center><math>f (x) = x^{2} + 5 \Rightarrow \lambda x.(x^{2} + 5)</math></center>
*<math>[X, Y]</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> можно различным образом.
 
Кроме образцов в функциональном программировании вводится такое понятие, как «клоз» (от англ. «clause»). По определению клозы выглядят так:
<tt>==></tt> <math>6</math>
 
На примере этого вычисления наглядно видно, что при рекурсивных вызовах функций очень сильно используется память. В данном случае количество памяти пропорционально значению аргумента, но аргументов может быть большее число, к примеру. Возникает резонный вопрос: можно ли так написать функцию вычисления факториала (и ей подобные), чтобы память использовалась минимально?
 
Чтобы ответить на данный вопрос положительно, необходимо рассмотреть понятие аккумулятора (накопителя). Для этого можно рассмотреть следующий пример:
#*<math>ReverseAll</math> — функция, получающая на вход списочную структуру и обращающая все её элементы, а также её саму.
#*<math>Position</math> — функция, возвращающая номер первого вхождения заданного атома в список.
#*<math>Set</math> — функция, возвращающая список из всех атомов, содержащийсодержащихся единичныев вхождениязаданном атомовсписке. Каждый атом должен присутствовать в результирующем списке в заданногоединственном спискачисле.
#*<math>Frequency</math> — функция, возвращающая список пар (символ, частота). Каждая пара определяет атом из заданного списка и частоту его вхождения в этот список.
#Написа́ть (если это возможно) функции с накапливающим параметром для заданий из '''[[Основы функционального программирования/Структуры данных и базисные операции#Упражнения|упражнения 1]]''' '''[[Основы функционального программирования/Структуры данных и базисные операции|лекции&nbsp;2]]'''.
Анонимный участник