Почему процедуры высшего порядка?
Так что, если язык обеспечивает процедуру более высокого порядка, тогда я могу иметь процедуру, которая возвращает процедуру. Что-то вроде:
(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 ответов
Это хорошее наблюдение, что функция, которая возвращает другую функцию, такая же, как функция, которая принимает два аргумента. Это называется "карри". Иными словами, функция от A до B является доказательством логического следствия того, что A подразумевает B, или:
A => B.
Как вы заметили, если A подразумевает, что B подразумевает C, то A и B подразумевают C, или:
(A => (B => C)) <==> ((A, B) => C)
Но функция более высокого порядка не обязательно является функцией, которая возвращает другую функцию. Функция более высокого порядка - это функция, которая принимает в качестве аргумента другую функцию. Это важное различие, и HOF - чрезвычайно мощные инструменты программирования.
Например, рассмотрим эту функцию Haskell:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : (map f xs)
Эта функция высшего порядка принимает функцию f и применяет его к каждому элементу в списке. В языках без HOF вы будете делать то, что делает эта функция с циклом или чем-то подобным, но на языке, в котором есть HOF, вы можете вызывать f для каждого элемента в списке с помощью простого вызова, как это:
map f myList
Конечно, управляющие конструкции в языках позволяют вам аппроксимировать функции высшего порядка, но язык, в котором есть функции высшего порядка, позволяет вам изобретать свои собственные управляющие конструкции. Схема, безусловно, достойна.
Я не буду пытаться резюмировать аргумент здесь, но в книге "Почему имеет значение функциональное программирование" Джон Хьюз утверждает, что функции более высокого порядка полезны, потому что они предоставляют более эффективные способы "склеивания" частей программы и тем самым облегчают ее выполнение. повторно использовать код. Примеры приведены на очень старом языке, который больше не используется, но они все еще просты для понимания и довольно убедительны. Чтение статьи Джона - хороший способ получить подробный ответ на ваш вопрос "почему так много размышлений о процедурах высшего порядка".
Хорошо, но во втором примере вы создаете эту процедуру во время компиляции с предопределенным списком a1, b1, а также c1, В первом примере вы создаете его во время выполнения, когда вызываете ProcAи вы можете создавать столько разных, сколько пожелаете, чтобы вы могли делать гораздо больше интересных вещей.
Это больше о мышлении, чем осуществимости. Это позволяет вам относиться к функциям как к первоклассным гражданам и думать с точки зрения функций, которые оперируют функциями для создания других функций и т. Д.
Очевидно, что вы могли бы сделать или смоделировать это с другими языками, но если это не синтаксический механизм, это воспринимается как дополнение или взлом.
Подумайте о функции преобразования или алгоритме сортировки по массиву. Теперь вы хотите сделать его действительно гибким, чтобы позволить пользователю вашей функции определять поведение вашей функции, позволяя ему передавать функцию в качестве аргумента.
Скажем, вы пишете алгоритм сортировки со следующим процедурным прототипом:
sort(Array a, void (*fn)(a::element_type, a::element_type));
Пользователь этой функции может указать, передав соответствующий fn, если он хочет упорядочить по убыванию или по возрастанию.
Я использую функции высшего порядка в javascript, например, когда я использую поле выбора. Я могу передать функцию, которая будет вызываться при выборе опции, поскольку единственное отличие для меня заключалось в том, что, что упрощает мой код, уменьшает избыточность.
Я вижу то же самое в других языках, которые я использую, которые поддерживают функции более высокого порядка, поскольку тогда я могу начать смотреть на то, как очистить мой код, где есть некоторая избыточность, которая может быть локализована, и любые различия могут быть сделаны в функция.
Когда C# поддерживал это, я знал, что это стало более распространенным явлением.:)
Вам потребуется внутренний класс, чтобы правильно имитировать это. В первом случае Proc замкнут над a, b и c. Во втором случае вызывающая сторона ProcA не может контролировать, как a1, b1 и c1 передаются другой процедуре, он может контролировать только x. Таким образом, способ управления a1, b1 и c1 заключается в использовании переменных с более высокой областью действия (на уровне модуля или некоторых других), что делает вашу функцию не чистой. В этом случае вы не можете гарантировать, что при одинаковых аргументах между вызовами ProcA будет возвращать один и тот же результат. Где, как и в случае с Proc, вы всегда можете быть уверены, что если вы вызовете его с одинаковыми аргументами, будут получены те же результаты.
Если функция принимает и / или возвращает функцию, она называется функцией высшего порядка (HOF). Для неопытных программистов, происходящих из C, C++ или Java, функции высшего порядка звучат как волшебство, но они очень просты. Представьте себе простую функцию, которая возвращает результат 2 + 3:
(define (foo) (+ 2 3)) ;; (foo) => 5
Это скучная функция, она всегда добавляет 2 к 3. Что если мы ее обобщим, чтобы она добавляла 2 не только к 3, но и к любому числу, предоставленному пользователем?
(define (foo n) (+ 2 n)) ;; (foo 10) => 12
Когда язык не поддерживает функции высшего порядка, вы вынуждены думать, что функции и значения (например, числа, логические значения, списки) - это две разные вещи. Но функциональное программирование (ФП) стирает различия между ними. Представьте, что единственное различие между функцией и значением состоит в том, что функция может быть вызвана, за исключением того, что вы можете делать с функцией все, что можете для 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))).
Таким образом, HOF позволяют нам обобщать наши функции, чтобы сделать их сверхгибкими. Если вы посмотрите на свою функцию, увидите логику, стоящую за ней, вы поймете, что если что-то воздействует на ваши данные, то, вероятно, тоже может что-то другое. Если вы сложите 2 числа вместе, вы, вероятно, могли бы умножить их, или вычесть, или возвести в степень одно в другое, или что-то еще. Вместо того, чтобы каждый раз писать новую функцию для каждого случая, вы можете просто принять дополнительный параметр, который должен быть функцией.
В FP мы используем HOF все время, например, при работе со списками. 3 функции - это хлеб с маслом FP: 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 арности - опять же, вы можете делать с функцией все, что хотите, и также сохранять ее в структуре данных - и вы хотите применить их все к одному и тому же номеру и получить список результатов.
(let ((xs (list (lambda (x) (+ x 1))
(lambda (x) (* x 2))
(lambda (x) (- x)))))
(map (lambda (f) (f 10)) xs)) ;; => (11 20 -10)
Вывод: когда язык программирования должным образом поддерживает концепции функционального программирования, функции высшего порядка обеспечивают гибкость и универсальность, что делает ваш код более мощным (вы можете использовать одну и ту же функцию для различных сценариев использования) и кратким (не нужно писать 10 версий). одной функции). Некоторые функции высшего порядка интенсивно используются в функциональном программировании, поэтому вы избавляетесь от низкоуровневых и подробных циклов for и пишете однострочники, которые делают все вместо этого.
Замечания: foldl, что аналогично "левому сгибу" или "левому уменьшению", является еще более мощным. Если вы действительно заинтересованы и у вас есть время, пожалуйста, прочитайте первую половину моего ответа, используя сокращение. Хотя он не написан для Scheme/Racket, но вместо этого для Common Lisp/Emacs Lisp, вы все равно можете понять идею, лежащую в основе Fold/ Reduce.