Почему процедуры более высокого порядка?

Таким образом, если язык предоставляет процедуру более высокого порядка, то я могу иметь процедуру, которая возвращает процедуру. Что-то вроде:

(define (Proc a b c)
  (lambda (x) ( #| method body here in terms of a b c and x |# )))

Чтобы создать новую процедуру, я бы просто сделал что-то вроде: 

(define ProcA (Proc a1 b1 c1)) ; Would create ProcA that has 1 argument

Аналогичная задача может быть выполнена в языке, который не поддерживает процедуру более высокого порядка, определив Proc, которая принимает 4 вместо 3 аргументов, и вызывая эту процедуру для определения ProcA, например: 

(define (Proc a b c x) ( #| method body -- does not return any procedure |# )
(define (ProcA x) (Proc a1 b1 c1 x))

Так почему же существует так много неясностей о процедуре более высокого порядка? Неужели я пропал? что-нибудь?

8 5
functional-programming programming-languages closures scheme abstraction

8 ответов:

Это хорошее наблюдение, что функция, возвращающая другую функцию, такая же, как и функция, принимающая два аргумента. Это называется "карринг". Другими словами, функция от A до B является доказательством логического вывода, что A подразумевает B, или: 

A => B.
Как вы заметили, если A подразумевает, что B подразумевает C, то A и B подразумевают C, или: 
(A => (B => C)) <==> ((A, B) => C)
Но функция более высокого порядка не обязательно является функцией, которая возвращает другую функцию. функция более высокого порядка - это функция, которая принимает в качестве аргумента другую функцию . Это важное отличие, а HOFs-чрезвычайно мощные инструменты программирования.

Например, рассмотрим такую функцию Хаскелла: 

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : (map f xs)
Эта функция более высокого порядка берет функцию f и применяет ее к каждому элементу в списке. В языках без HOFs вы бы сделали то же, что эта функция делает с циклом или чем-то подобным, но в языке, который имеет HOFs, вы можете вызвать f для каждого элемента в списке простым вызовом вот так: 
map f myList
Конечно, управляющие конструкции в языках позволяют аппроксимировать функции более высокого порядка, но язык, в котором есть функции более высокого порядка, позволяет создавать собственные управляющие конструкции. Схема безусловно квалифицирует.
8

Я не буду пытаться повторить этот аргумент здесь, но в Why Functional Programming Matters, Джон Хьюз утверждает, что функции более высокого порядка полезны, потому что они обеспечивают более эффективные способы "склеивания" частей программы, и тем самым облегчают повторное использование кода. Примеры приведены на очень старом языке, который больше не используется много, но они по-прежнему легко следовать и довольно убедительны. Чтение статьи Джона-хороший способ получить подробный ответ на свой вопрос "почему так много путают о процедурах высшего порядка".

3

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

Очевидно, что вы можете сделать или смоделировать это с другими языками, но если это не синтаксический механизм, то он рассматривается как дополнение или Хак.

1

Хорошо, но во втором примере вы создаете эту процедуру во время компиляции с заранее определенным списком a1, b1, и c1. В первом примере вы создаете его во время выполнения, когда вызываете ProcA, и вы можете создавать столько различных объектов, сколько захотите, поэтому вы можете делать гораздо более интересные вещи.

1

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

Предположим, вы пишете алгоритм сортировки со следующим процедурным прототипом: 
sort(Array a, void (*fn)(a::element_type, a::element_type));

Пользователь этой функции может указать, передавая соответствующий fn, требуется ли ему нисходящий или восходящий порядок.

1

Вам понадобится внутренний класс, чтобы правильно смоделировать это. В первом случае Proc закрывается над a, b и c. во втором случае вызывающий ProcA не может контролировать, как a1, b1 и c1 передаются другой процедуре, он может только управлять x. таким образом, способ управления a1, b1 и c1 осуществляется через переменные use на более высоком уровне (уровень модуля или что-то подобное), что делает вашу функцию не чистой. В этом случае вы не можете гарантировать, что при одинаковых аргументах между вызовами ProcA вернет тот же результат. Где, как и в случае с Proc, вы всегда можете быть уверены, что если вы вызовете его с теми же аргументами, то получите те же результаты.

0

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

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

Как только C# поддержал это,я знал, что теперь это стало более распространенным. :)

0

Если функция принимает и/или возвращает функцию, она называется функцией более высокого порядка (HOF). Для неопытных программистов, пришедших из C, C++ или Java, функции более высокого порядка звучат как магия, но они очень просты. Представьте себе простую функцию, которая возвращает результат 2 + 3: 

(define (foo) (+ 2 3)) ;; (foo) => 5

Это скучная функция, она всегда добавляет 2 к 3. Что, если мы обобщим его, так что он добавит 2 не только к 3, но и к любому пользовательскому числу?

(define (foo n) (+ 2 n)) ;; (foo 10) => 12

Когда язык не поддерживает функции более высокого порядка, вы вынуждены думать, что функции и значения (например, числа, булевы числа, списки) - это две разные вещи. Нофункциональное программирование (FP) стирает различие между ними. Представьте себе, что единственное различие между функцией и значением состоит в том, что функцию можно вызвать, кроме того, что вы можете сделать с функцией все, что вы могли бы сделать с 2 или #t или '(a b c): вы могли бы дать ее в качестве аргумента, или вернуть из функции, или сохранить в переменной, или внесите это в список. Например, давайте обобщим нашу маленькую функцию дальше, чтобы она могла не только добавить 2 к n, но и умножить 2 на n, или применить любую другую функцию, которая будет принимать два числа: 

(define (foo f n) (f 2 n))
;; (foo + 10) => 12
;; (foo * 10) => 20
;; (foo expt 10) => 1024

Когда вы понимаете, что функция может быть обработана так же, как число или строка, анонимные функции (называемые "лямбды" на жаргоне FP) имеют полный смысл. Анонимные функции на самом деле являются более простыми и "нормальными", чем обычные именованные функции, именованные функции-это просто анонимные функции, помещенные в переменную, точно так же, как мы помещаем число в переменную, чтобы использовать его несколько раз.

(+ 2 2) ;; is no different from:
(let ((a 2)) (+ a a))
(lambda (x y) (* x y)) ;; is no different from:
(define (foo x y) (* x y)) ;; which is an abbreviation for:
(define foo (lambda (x y) (* x y))).
Таким образом, HOFs позволяет нам обобщать наши функции, чтобы сделать их сверхгибкими. Если вы посмотрите на свою функцию, увидите логику, стоящую за ней, вы можете понять, что если что-то работает с вашими данными, то что-то другое, вероятно, тоже может. Если вы сложите 2 числа вместе, вы, вероятно, можете умножить их, или вычесть, или возведение в степень один в другой, или что угодно. Вместо того чтобы каждый раз писать новую функцию для каждого случая, вы можете просто принять дополнительный параметр, который должен быть функцией.

В FP мы постоянно используем HOFs, например, при работе со списками. 3 функции являются хлебом и маслом ФП: map, filter и еще foldl. map принимает функцию с 1 аргументом, применяет эту функцию к каждому элементу списка и возвращает новый список с измененными элементами. filter принимает предикат (функция, возвращающая логическое значение) с аргументом 1, применяет предикат к каждому элементу списка и возвращает новый список с элементами, которые не удовлетворяют удаленному предикату.

(map (lambda (n) (+ n 1)) '(1 2 3 4 5) ;; '(2 3 4 5 6)
(define (foo n) (+ n 1))
(map foo '(1 2 3 4 5)) ;; '(2 3 4 5 6)
(filter (lambda (n) (> n 3)) '(1 2 3 4 5)) ;; '(4 5)
(define (bar n) (> n 3))
(filter bar '(1 2 3 4 5)) ;; '(4 5)
Представьте, что у вас есть список функций 1-arity-опять же, вы можете делать с функцией все, что хотите, и хранить ее в структуре данных,-и вы хотите применить все из них к одному и тому же числу и получить список результатов. 
(let ((xs (list (lambda (x) (+ x 1))
                (lambda (x) (* x 2))
                (lambda (x) (- x)))))
  (map (lambda (f) (f 10)) xs)) ;; => (11 20 -10)

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

Примечание: foldl, что то же самое, что "левая складка" или "левая редукция", еще более мощно. Если вам действительно интересно и у вас есть время, пожалуйста, прочитайте первую половину моего ответа, используя reduce. Хотя он не написан для Scheme/Racket, но вместо этого для Common Lisp/Emacs Lisp, вы все еще можете понять идею fold/reduce.

0