¿Por qué procedimientos de orden superior?

Question

Entonces, si un idioma proporciona un procedimiento de orden superior, entonces puedo tener un procedimiento que devuelva el procedimiento. Algo así como:

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

Para crear un nuevo procedimiento, simplemente haría algo como:

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

Se podría realizar una tarea similar en un lenguaje que no admite procedimientos de orden superior definiendo Proc que toma 4 en lugar de 3 argumentos y llamando a este procedimiento para definir ProcA , como:

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

Entonces, ¿por qué hay tanta confusión sobre el procedimiento de orden superior? ¿Me estoy perdiendo algo?

Answer 1

Es una buena observación que una función que devuelve otra función es lo mismo que una función que toma dos argumentos. Esto se llama "Curry". Dicho de otra manera, una función de A a B es prueba de una implicación lógica, que A implica B, o:

A => B.

Como notará, si A implica que B implica C, entonces A y B implica C, o:

(A => (B => C)) <==> ((A, B) => C)

Pero una función de orden superior no es necesariamente una función que devuelve otra función. Una función de orden superior es una función que toma otra función como argumento . Esta es una diferencia importante, y los HOF son herramientas de programación inmensamente poderosas.

Por ejemplo, considere esta función de Haskell:

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : (map f xs)

Esta función de orden superior toma una función f y la aplica a cada elemento de una lista. En idiomas sin HOF, haría lo que hace esta función con un bucle o algo similar, pero en un lenguaje que tiene HOF, puede llamar a f para cada elemento de la lista con una simple llamada como esta :

map f myList

Claro, las construcciones de control en idiomas le permiten aproximar las funciones de orden superior, pero un lenguaje que tiene funciones de orden superior le permite inventar sus propias construcciones de control . El esquema ciertamente califica.

Answer 2

No intentaré recapitular el argumento aquí, pero en ¿Por qué? Asuntos de programación funcional , John Hughes argumenta que las funciones de orden superior son útiles porque proporcionan formas más efectivas de "pegarse". partes de un programa y, por lo tanto, facilitan la reutilización del código. Los ejemplos están en un lenguaje muy antiguo que ya no se usa mucho, pero siguen siendo fáciles de seguir y bastante convincentes. Leer el artículo de John es una buena manera de obtener una respuesta detallada a su pregunta "por qué hay tanta confusión sobre los procedimientos de orden superior".

Answer 3

Esto se trata más de mentalidad que de viabilidad. Le permite tratar las funciones como ciudadanos de primera clase y pensar en términos de funciones que operan en funciones para crear otras funciones, etc.

Obviamente, podría hacer o simular esto con otros idiomas, pero si no es un mecanismo sintáctico, se trata como una adición o un truco.

Answer 4

OK, pero en el segundo ejemplo, está creando ese procedimiento en tiempo de compilación con una lista ordenada previamente de a1 , b1 y c1 . En el primer ejemplo, lo está creando en tiempo de ejecución cuando llama a ProcA , y puede crear tantos diferentes como desee, para que pueda hacer cosas mucho más interesantes.

Answer 5

Piense en una función de transformación o un algoritmo de clasificación a través de una matriz. Ahora, desea que sea realmente flexible para permitir que el usuario de su función especifique el comportamiento de su función permitiéndole pasar una función como argumento.

Digamos que escribes un algoritmo de clasificación con el siguiente prototipo de procedimiento:

sort(Array a, void (*fn)(a::element_type, a::element_type));

El usuario de esa función podría especificar, pasando el fn apropiado, si desea un orden descendente o ascendente.

Answer 6

Necesitarías una clase interna para simular eso correctamente. El primer caso, Proc se cierra sobre a, byc. En el segundo caso, la persona que llama de ProcA no puede controlar cómo se pasan a1, b1 y c1 al otro procedimiento, solo puede controlar x. Entonces, la forma en que controla a1, b1 y c1 es a través de las variables de uso en un ámbito más alto (nivel de módulo o algo así), lo que hace que su función no sea pura. En ese caso, no puede asegurarse de que dados los mismos argumentos en todas las llamadas, ProcA devolverá el mismo resultado. Mientras que con Proc, siempre puede estar seguro de que si lo llama con los mismos argumentos, se obtendrán los mismos resultados.

Answer 7

Uso funciones de orden superior en javascript, por ejemplo, cuando uso un cuadro de selección. Puedo pasar la función que se llamará cuando se seleccione una opción, ya que la única diferencia para mí fue que, lo que simplifica mi código, reduce la redundancia.

Veo lo mismo en otros idiomas que uso que admite funciones de orden superior, ya que puedo comenzar a ver cómo limpiar mi código, donde hay algo de redundancia que se puede localizar, y cualquier diferencia puede ser hecho en una función.

Una vez que C # apoyó esto, supe que ahora era más convencional. :)

Answer 8

Si una función acepta y / o devuelve una función, se llama función de orden superior (HOF). Para programadores sin experiencia, provenientes de C, C ++ o Java, las funciones de orden superior suenan mágicas, pero son muy simples. Imagine una función simple que devuelve el resultado de 2 + 3:

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

Esa es una función aburrida, siempre agrega 2 a 3. ¿Qué pasa si la generalizamos, de modo que agrega 2 no solo a 3, sino a cualquier número proporcionado por el usuario?

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

Cuando un idioma no admite funciones de orden superior, se ve obligado a pensar que las funciones y los valores (por ejemplo, números, booleanos, listas) son dos cosas distintas. Pero programación funcional (FP) difumina la distinción entre ellos. Imagine que la única diferencia entre una función y un valor es que se puede llamar a una función, además de que puede hacer con una función lo que sea posible con un 2 o #t o '(abc) : puede darlo como argumento, o regresar de una función, o almacenarlo en una variable, o ponerlo en una lista. Por ejemplo, generalicemos aún más nuestra pequeña función, por lo que no solo podría agregar 2 a n , sino multiplicar 2 por n , o aplicar cualquier otra función que acepte dos números :

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

Cuando se da cuenta de que una función se puede tratar de la misma manera que se trata un número o una cadena, anónimo funciones (llamadas "lambdas" en la jerga FP) tienen sentido completo. Las funciones anónimas son en realidad más básicas y "normales" que las funciones con nombre ordinarias, las funciones con nombre son solo funciones anónimas puestas en una variable, al igual que ponemos un número en una variable para usarla varias veces.

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

Entonces, los HOF nos permiten generalizar nuestras funciones para hacerlas súper flexibles. Si observa su función, ve la lógica detrás de ella, puede darse cuenta de que si algo opera en sus datos, entonces algo más probablemente también podría hacerlo. Si suma 2 números, probablemente podría multiplicarlos, restar o exponer uno a otro, o lo que sea. En lugar de escribir una nueva función para cada caso cada vez, puede aceptar un parámetro adicional, que debe ser una función.

En FP usamos HOF todo el tiempo, por ejemplo, al manipular listas. 3 funciones son pan y mantequilla de FP: map , filter y foldl . map acepta una función con 1 argumento, aplica esta función a cada elemento de una lista y devuelve una nueva lista con elementos modificados. filter acepta un predicado (función que devuelve un valor booleano) con 1 argumento, aplica el predicado a cada elemento de una lista y devuelve una nueva lista con elementos que no satisfacen el predicado eliminado.

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

Imagina que tienes una lista de funciones de 1 aridad, de nuevo, puedes hacer lo que quieras con una función y almacenarla también en una estructura de datos, y quieres aplicarlas todas al mismo número, y obtener una lista de resultados.

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

Conclusión: cuando un lenguaje de programación admite adecuadamente los conceptos de programación funcional, las funciones de orden superior permiten flexibilidad y generalidad, lo que hace que su código sea más poderoso (puede