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

StackOverflow https://stackoverflow.com/questions/832668

Вопрос

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

(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))

Так почему в процедуре высшего порядка так много шума? Я что-то упустил?

Это было полезно?

Решение

Это хорошее наблюдение, что функция, которая возвращает другую функцию, такая же, как функция, которая принимает два аргумента. Это называется "карри". Другими словами, функция от 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, хочет ли он упорядочения по убыванию или по возрастанию.

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

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

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

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

Если функция принимает и / или возвращает функцию, она называется функцией более высокого порядка (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 или '(abc) : вы можете указать его в качестве аргумента, либо вернуть из функции, либо сохранить в переменной, либо поместить в список. Например, давайте обобщим нашу маленькую функцию, чтобы она не только добавила 2 к n , но и умножила 2 на n или применила любую другую функцию, которая бы принимала два числа 

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

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

(+ 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-арных функций & # 8212; опять же, вы можете делать с функцией все, что хотите, и также сохранять ее в структуре данных & # 8212; и вы хотите применить их все к тот же номер, и получите список результатов. 

(let ((xs (list (lambda (x) (+ x 1))
                (lambda (x) (* x 2))
                (lambda (x) (- x)))))
  (map (lambda (f) (f 10)) xs)) ;; => (11 20 -10)

Заключение: когда язык программирования должным образом поддерживает концепции функционального программирования, функции высшего порядка обеспечивают гибкость и универсальность, что делает ваш код более мощным (вы можете

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top