Cтраница 3
В этой главе будет рассмотрено еще одно важное средство функциональных языков, а именно функции высшего порядка. Концепция функций высшего порядка возникает из идеи о том, что функции должны иметь тот же статус, что и любой объект данных, так чтобы они сами могли быть входными и выходными данными других функций. В этой главе будет показано, Каким образом эта способность может быть использована для представления общих образцов рекурсии и, следовательно, для выражения рекурсивных функций через нерекурсивное применение функций высшего порядка. Подобная техника приводит к очень сжатым и абстрактным программам, которые часто просто удивительно коротки по сравнению со сложностью выполняемых ими вычислений. Мы рассмотрим также определенный стиль программирования, основанный на использовании функций высшего порядка, и несколько, примеров, иллюстрирующих его применение на практике. [31]
Функция высшего порядка - это функция, которая может использовать в качестве аргумента другую функцию либо результатом ее выполнения является некая функция. Если быть более точным, то функция первого порядка имеет тип А - - В, где в выражениях А и В нет стрелок. Таким образом, можно сказать, что функция высшего порядка - это любая функция, не являющаяся функцией первого порядка. [32]
Приведенные четыре примера должны продемонстрировать особенности одного из стилей программирования на базе функциональных языков, в данном случае - Норе, названного систематической дефиницией функций, определенных на типах данных. Структура задачи моментально подсказывает структуру решения, а структура типа данных - структуру каждой функции. Однако на базе функциональных языков существуют и другие стили программирования. Наиболее важные из них включают в себя использования функций высшего порядка и ленивого вычисления. Эти особенности языка Норе будут рассмотрены в последних двух главах. [33]
Ограничением при использовании F является в этом случае запрет частичного применения F. Если мы применяем F частично, то не имеем механизма, с помощью которого можно ссылаться на результирующую функцию, и не имеем механизма применения такой функции. Тем не менее именно таким путем реализуется применение функций во многих традиционных потоковых машинах. Невозможность поддерживать ( по крайней мере, простым способом) функции высшего порядка делает эти машины очень неудобными для реализации функциональных языков. [34]
Однако Норе никоим образом не является ни единственным, ни окончательным ( в любом смысле этого слова) функциональным языком. Как мы видели, важными особенностями функционального языка, отличающими его от языка любого другого типа, являются прозрачность ссылок и детерминизм. Это оставляет значительный простор для вариаций в таких областях, как строгая типизация, определенные пользователем типы данных, функции высшего порядка и правила вычисления, а также для косметических различий, например в синтаксисе языка. [35]
На этом заканчивается описание основных компонентов FP-системы. В следующем разделе мы коротко обсудим стиль программирования на языке FP. Этот вопрос представляет здесь скорее академический интерес, поскольку мы будем использовать FP в основном как инструмент описания преобразований, а не как инструмент разработки программного обеспечения. Однако, как мы увидим далее, FP хорошо иллюстрирует мощность функциональной нотации, и в особенности выразительную силу функций высшего порядка. [36]
Теперь мы определим операции, связанные с каждым из шести различных типов вершин. Это требует минимальных объяснений. Исключением является вершина применения, с которой связана операция подстановки ПГ, представляющего функцию пользователя, и операция построения и применения частичных применений, которые мы снова называем замыканиями. Определив все конституенты ПГ, мы покажем в качестве примеров ПГ двух функций: функции первого порядка для вычисления чисел Фибоначчи и функции высшего порядка тар, которая применяет заданную функцию к каждому элементу заданного списка. [37]
В этой главе будет рассмотрено еще одно важное средство функциональных языков, а именно функции высшего порядка. Концепция функций высшего порядка возникает из идеи о том, что функции должны иметь тот же статус, что и любой объект данных, так чтобы они сами могли быть входными и выходными данными других функций. В этой главе будет показано, Каким образом эта способность может быть использована для представления общих образцов рекурсии и, следовательно, для выражения рекурсивных функций через нерекурсивное применение функций высшего порядка. Подобная техника приводит к очень сжатым и абстрактным программам, которые часто просто удивительно коротки по сравнению со сложностью выполняемых ими вычислений. Мы рассмотрим также определенный стиль программирования, основанный на использовании функций высшего порядка, и несколько, примеров, иллюстрирующих его применение на практике. [38]
Поэтому эти функционалы составляют фиксированный набор комбинаторов. В этом разделе мы рассмотрим сначала подмножество первого порядка языка FP и опишем неформально набор комбинаторов, естественных для определения функциональных выражений. С более практической точки зрения любой функциональный язык, такой как Норе, просто транслировать в категорийную комбинаторную форму. FP функций первого порядка, использующих как сопоставле-ние ] с образцом, так и определенные пользователем составные тиг ы данных; расширение для случая категорийных комбинаторов и функций высшего порядка является непосредственным. [39]