Cтраница 2
Функции, которые в качестве параметров используют другие функции или же возвращают их как результат своей работы, называются функциями высшего порядка. [16]
Однако при этом допускалось бы частичное применение функции арности п 2 к менее чем п аргументам, дающее в результате функцию высшего порядка. [17]
Как и у функций Лежандра в § 5, процессом дифференцирования и умножения на подходящие множители приходим и здесь к лагерровским функциям высшего порядка ( обобщенные функции Лагерра), которые удовлетворяют аналогичным дифференциальным уравнениям. [18]
После завершения написания этой программы мы увидим, каким образом Treesort, представленная в предыдущей главе, может быть расширена для сортировки подобных пар различным образом путем трансформации ее в функцию высшего порядка. Итак, пусть исходный текст составляют предложения, разделенные точками, а каждое предложение есть совокупность слов, разделенных одним или несколькими пробелами. Для простоты определим слово как любую последовательность символов, исключая пробелы и точки. [19]
Функция высшего порядка - это функция, которая может использовать в качестве аргумента другую функцию либо результатом ее выполнения является некая функция. Если быть более точным, то функция первого порядка имеет тип А - - В, где в выражениях А и В нет стрелок. Таким образом, можно сказать, что функция высшего порядка - это любая функция, не являющаяся функцией первого порядка. [20]
В этой главе будет рассмотрено еще одно важное средство функциональных языков, а именно функции высшего порядка. Концепция функций высшего порядка возникает из идеи о том, что функции должны иметь тот же статус, что и любой объект данных, так чтобы они сами могли быть входными и выходными данными других функций. В этой главе будет показано, Каким образом эта способность может быть использована для представления общих образцов рекурсии и, следовательно, для выражения рекурсивных функций через нерекурсивное применение функций высшего порядка. Подобная техника приводит к очень сжатым и абстрактным программам, которые часто просто удивительно коротки по сравнению со сложностью выполняемых ими вычислений. Мы рассмотрим также определенный стиль программирования, основанный на использовании функций высшего порядка, и несколько, примеров, иллюстрирующих его применение на практике. [21]
Хотя эти примеры просты, они дают представление о стиле программирования на языке FP. Фактически элегантность нерекурсивных решений в равной степени говорит о выразительной силе как функций высшего порядка, так и языка FP в целом. В языках, подобных Норе, основанных на объектах, мы можем получить похожие решения этих задач, используя описанные ранее функции тар и reduce. Хотя можно возразить, что FP, не имея строгой типизации и имея только последовательности для построения структур данных, недостаточно хорошо оснащен для использования в серьезных программных разработках, существует много преимуществ в предписываемой этим языком, свободной от переменных манере программирования. В действительности нет причин, по которым нельзя было бы соответствующим образом дополнить FP, и эта работа была начата в проекте языка FL [9], который сохраняет свободный от переменных стиль программирования. [22]
Заметим, что первая редукция заключается в подстановке вместо / функции ( Ку. Это вполне приемлемо; абстракция, содержащая /, соответствует тому, что было бы функцией высшего порядка в эквивалентной исходной программе. [23]
В приведенном примере программы rev аргументы каждой функции разделяются пробелами, а не заключаются все вместе в скобки. Причина такой формы записи в том, что каждая функция в языке Miranda является по существу функцией высшего порядка. [24]
Другая проблема состоит в выборе решающего правила или, что тоже самое, математического вида разделяющей функции. На рис. 85 показана ситуация, когда задачу нельзя решить при помощи функции линейного вида. Необходима либо функция высшего порядка, либо ее кусочная аппроксимация. [25]
При этом, если k n, выражение представляет частичное применение этого примитива и, как мы отмечали в гл. СЗНФ, поскольку такое применение примитива нельзя редуцировать, пока отсутствуют недостающие k - п аргументов. G должна быть функцией высшего порядка. [26]
Идея такой классификации заключается в том, что можно представить себе ситуации, в которых для описания задачи достаточно знать одну, две или некоторое конечное число функций Wn. Иными словами, в некоторых случаях функцию высшего порядка Wn можно выразить через функции низших порядков. Здесь заложена та же самая идея, что и в процедурах расцепления цепочки уравнений для частичных функций распределения, о чем говорилось в разд. Однако мы не станем проводить исчерпывающую систематическую классификацию, а рассмотрим лишь два первых класса. [27]
Итак, закончено обсуждение, функций высшего порядка и приемов программирования этих функций. Следует отметить, что в Норе, как и в большинстве функциональных языков, не существует ограничений на количество и сложность подобных функций. FP, в котором нет средств для определения пользователем функций высшего порядка. Вместо этого язык обеспечен небольшим набором встроенных функций высшего порядка, которые рассматриваются как программно-встроенные блоки типа let, where, условные выражения и др., которые в языке Норе обеспечивают построение программных блоков. [28]
Использование лямбда-вычисления является достаточным для нашего синтаксиса выражений, так как нам известно, что с его помощью можно представить любой функциональный язык и соответствующий способ трансляции. Для представления функций от более чем одного параметра, мы можем ввести в лямбда-вычисления кортежи, как было предложено в гл. Однако при доказательстве надежности, основанном на предлагаемом ниже подходе, в любом случае допускается наличие функций высшего порядка и предполагается, что все функции представлены в карринговой форме. [29]
Аксиомы, связанные с примитивными функционалами FP, будут использоваться чрезвычайно широко, поскольку они определяют структуру определений функций, подлежащих преобразованию Предлагаемое множество аксиом не является полным в том смысле, что существуют равенства между функциями, невыводимые из аксиом. Наиболее важные аксиомы связаны с комбинированными формами из композиции, условия и конструкции, существенных для определения полезных функций первого порядка. Любое, включающее другие комбинированные формы, выражение эквивалентно одному из определенных в терминах явно рекурсивных функций, которые используют только эти три формы, использование функций высшего порядка обсуждалось в гл. [30]