function haskell functional-programming combinators higher-order-functions

function - ¿Cuáles son algunos usos interesantes de las funciones de orden superior?



haskell functional-programming (14)

Aquí hay un patrón que no he visto a nadie más mencionar y que realmente me sorprendió la primera vez que lo supe. Considere un paquete de estadísticas donde tenga una lista de muestras como su entrada y desee calcular un grupo de estadísticas diferentes sobre ellas (también hay muchas otras formas de motivar esto). La conclusión es que tiene una lista de funciones que desea ejecutar. ¿Cómo los ejecutas?

statFuncs :: [ [Double] -> Double ] statFuncs = [minimum, maximum, mean, median, mode, stddev] runWith funcs samples = map ($samples) funcs

Aquí hay todo tipo de bondades de orden superior, algunas de las cuales se han mencionado en otras respuestas. Pero quiero señalar la función ''$''. Cuando vi por primera vez este uso de ''$'', me quedé impresionado. Antes de eso no había considerado que fuera muy útil más que como un reemplazo conveniente para paréntesis ... pero esto era casi mágico ...

Actualmente estoy haciendo un curso de Programación Funcional y me divierte mucho el concepto de funciones y funciones de orden superior como ciudadanos de primera clase. Sin embargo, todavía no puedo pensar en muchas funciones de orden superior, prácticamente útiles, conceptualmente sorprendentes o simplemente interesantes. (Además de las funciones típicas y bastante aburridas de map , filter , etc.).

¿Conoces ejemplos de funciones tan interesantes?

Tal vez funciones que devuelven funciones, funciones que devuelven listas de funciones (?), Etc.

Apreciaría ejemplos en Haskell, que es el idioma que estoy aprendiendo actualmente :)

Aquí hay un pequeño fragmento de code parafraseado:

rays :: ChessPieceType -> [[(Int, Int)]] rays Bishop = do dx <- [1, -1] dy <- [1, -1] return $ iterate (addPos (dx, dy)) (dx, dy) ... -- Other piece types -- takeUntilIncluding is an inclusive version of takeUntil takeUntilIncluding :: (a -> Bool) -> [a] -> [a] possibleMoves board piece = do relRay <- rays (pieceType piece) let ray = map (addPos src) relRay takeUntilIncluding (not . isNothing . pieceAt board) (takeWhile notBlocked ray) where notBlocked pos = inBoard pos && all isOtherSide (pieceAt board pos) isOtherSide = (/= pieceSide piece) . pieceSide

Esto usa varias funciones de "orden superior":

iterate :: (a -> a) -> a -> [a] takeUntilIncluding -- not a standard function takeWhile :: (a -> Bool) -> [a] -> [a] all :: (a -> Bool) -> [a] -> Bool map :: (a -> b) -> [a] -> [b] (.) :: (b -> c) -> (a -> b) -> a -> c (>>=) :: Monad m => m a -> (a -> m b) -> m b

(.) es el . operador, y (>>=) es el operador de salto de línea " do -notación".

Cuando programe en Haskell, simplemente utilícelos. Donde no tienes las funciones de orden superior es cuando te das cuenta de cuán increíblemente útiles eran.

Bueno, ¿notas que Haskell no tiene sintaxis para los bucles? No while o do o for . Porque estas son solo funciones de orden superior:

map :: (a -> b) -> [a] -> [b] foldr :: (a -> b -> b) -> b -> [a] -> b filter :: (a -> Bool) -> [a] -> [a] unfoldr :: (b -> Maybe (a, b)) -> b -> [a] iterate :: (a -> a) -> a -> [a]

Las funciones de orden superior reemplazan la necesidad de sintaxis cocida en el lenguaje para las estructuras de control, lo que significa que casi todos los programas Haskell usan estas funciones, ¡haciéndolas bastante útiles!

Son el primer paso hacia una buena abstracción porque ahora podemos conectar el comportamiento personalizado en una función de esqueleto de propósito general.

En particular, las monads solo son posibles porque podemos encadenar y manipular funciones para crear programas.

El hecho es que la vida es bastante aburrida cuando es de primer orden. La programación solo se vuelve interesante una vez que tienes orden superior.

Joel Spolsky escribió un famoso ensayo que demuestra cómo Map-Reduce funciona usando las funciones de orden superior de Javascript. Una lectura obligada para cualquiera que haga esta pregunta.

Martín Escardó ofrece un ejemplo interesante de una función de orden superior :

equal :: ((Integer -> Bool) -> Int) -> ((Integer -> Bool) -> Int) -> Bool

Dados dos funcionales f, g :: (Integer -> Bool) -> Int , entonces equal fg decide si f y g son (extensionalmente) iguales o no, aunque f y g no tengan un dominio finito. De hecho, el codominio, Int , puede ser reemplazado por cualquier tipo con una igualdad decidible.

El código que da Escardó está escrito en Haskell, pero el mismo algoritmo debería funcionar en cualquier lenguaje funcional.

Puede usar las mismas técnicas que describe Escardó para calcular integrales definidas de cualquier función continua con precisión arbitraria.

Muchas técnicas utilizadas en la programación OO son soluciones para la falta de funciones de orden superior.

Esto incluye una serie de patrones de diseño omnipresentes en la programación funcional. Por ejemplo, el patrón de visitante es una forma bastante complicada de implementar un fold . La solución consiste en crear una clase con métodos y pasar un elemento de la clase como un argumento, como un sustituto para pasar una función.

El patrón de strategy es otro ejemplo de un esquema que a menudo pasa objetos como argumentos como un sustituto de lo que realmente se pretende, funciones.

De manera similar, la inyección de dependencia a menudo implica un esquema poco claro para pasar un proxy para funciones cuando a menudo sería mejor simplemente pasar las funciones directamente como argumentos.

Entonces mi respuesta sería que las funciones de orden superior a menudo se usan para realizar el mismo tipo de tareas que realizan los programadores OO, pero directamente, y con mucho menos repetitivo.

Realmente comencé a sentir el poder cuando aprendí que una función puede ser parte de una estructura de datos. Aquí hay una "mónada de consumidor" (technobabble: mónada libre (i ->) ).

data Coro i a = Return a | Consume (i -> Coro i a)

Entonces, un Coro puede arrojar un valor instantáneamente o ser otro Coro dependiendo de alguna entrada. Por ejemplo, esto es un Coro Int Int :

Consume $ /x -> Consume $ /y -> Consume $ /z -> Return (x+y+z)

Esto consume tres entradas enteras y devuelve su suma. También podría hacer que se comporte de manera diferente según las entradas:

sumStream :: Coro Int Int sumStream = Consume (go 0) where go accum 0 = Return accum go accum n = Consume (/x -> go (accum+x) (n-1))

Esto consume un Int y luego consume muchos Ints más antes de ceder su suma. Esto se puede considerar como una función que toma arbitrariamente muchos argumentos, construidos sin ningún lenguaje mágico, solo funciones de orden superior.

Las funciones en las estructuras de datos son una herramienta muy poderosa que no formaba parte de mi vocabulario antes de comenzar a hacer Haskell.

Se ha mencionado que Javascript admite ciertas funciones de orden superior, incluido un ensayo de Joel Spolsky . Mark Jason Dominus escribió un libro completo llamado Higher-Order Perl ; la fuente del libro está disponible para su descarga gratuita en una variedad de formatos finos, incluido PDF .

Desde al menos Perl 3, Perl ha admitido funcionalidades que recuerdan más a Lisp que a C, pero no fue hasta Perl 5 cuando se pudo disponer del soporte completo para cierres y todo lo que sigue de eso. Y una de las primeras implementaciones de Perl 6 fue escrita en Haskell, que ha tenido mucha influencia sobre cómo ha progresado el diseño de ese lenguaje.

Ejemplos de enfoques de programación funcional en Perl aparecen en la programación diaria, especialmente con map y grep :

@ARGV = map { //.gz$/ ? "gzip -dc < $_ |" : $_ } @ARGV; @unempty = grep { defined && length } @many;

Dado que el sort también admite un cierre, el patrón de map/sort/map es muy común:

@txtfiles = map { $_->[1] } sort { $b->[0] <=> $a->[0] || lc $a->[1] cmp lc $b->[1] || $b->[1] cmp $a->[1] } map { -s => $_ } grep { -f && -T } glob("/etc/*");

o

@sorted_lines = map { $_->[0] } sort { $a->[4] <=> $b->[4] || $a->[-1] cmp $b->[-1] || $a->[3] <=> $b->[3] || ... } map { [$_ => reverse split /:/] } @lines;

La función de reduce facilita la lista de hackers sin bucles:

$sum = reduce { $a + $b } @numbers; $max = reduce { $a > $b ? $a : $b } $MININT, @numbers;

Hay mucho más que esto, pero esto es solo un gusto. Los cierres facilitan la creación de generadores de funciones, al escribir sus propias funciones de orden superior, y no solo al utilizar los builtins. De hecho, uno de los modelos de excepciones más comunes,

try { something(); } catch { oh_drat(); };

no es un built-in. Sin embargo, se define casi trivialmente como una función que toma dos argumentos: un cierre en el primer arg y una función que tiene un cierre en el segundo.

Perl 5 no tiene currying incorporado, aunque hay un módulo para eso. Sin embargo, Perl 6 tiene currying y continuaciones de primera clase incorporadas, además de mucho más.

Soy un fanático particular de la memorización de orden superior:

memo :: HasTrie t => (t -> a) -> (t -> a)

(Dada cualquier función, devuelva una versión memorada de esa función. Limitado por el hecho de que los argumentos de la función deben poder codificarse en un trie).

Esto es de http://hackage.haskell.org/package/MemoTrie

También se requieren funciones de orden superior para currying , que Haskell usa en todas partes. Esencialmente, una función que toma dos argumentos es equivalente a una función que toma un argumento y devuelve otra función tomando un argumento. Cuando vea una firma de tipo como esta en Haskell:

f :: A -> B -> C

... el (->) se puede leer como asociativo de la derecha, lo que muestra que, de hecho, se trata de una función de orden superior que devuelve una función de tipo B -> C :

f :: A -> (B -> C)

Una función no currificada de dos argumentos tendría un tipo como este:

f'' :: (A, B) -> C

Entonces, cada vez que usa una aplicación parcial en Haskell, está trabajando con funciones de orden superior.

Una cosa interesante y ligeramente loca que puede hacer es simular un sistema orientado a objetos usando una función y almacenando datos en el alcance de la función (es decir, en un cierre). Es de orden superior en el sentido de que la función del generador de objetos es una función que devuelve el objeto (otra función).

Mi Haskell está bastante oxidado, así que no puedo darte fácilmente un ejemplo de Haskell, pero aquí hay un ejemplo simplificado de Clojure que con suerte transmite el concepto:

(defn make-object [initial-value] (let [data (atom {:value initial-value})] (fn [op & args] (case op :set (swap! data assoc :value (first args)) :get (:value @data)))))

Uso:

(def a (make-object 10)) (a :get) => 10 (a :set 40) (a :get) => 40

El mismo principio funcionaría en Haskell (excepto que probablemente necesitarías cambiar la operación establecida para devolver una nueva función ya que Haskell es puramente funcional)

Una cosa que es divertida, si no particularmente práctica, es Church Numerals . Es una forma de representar enteros usando nada más que funciones. Loco, lo sé. <shamelessPlug> Aquí hay una implementación en JavaScript que hice. Puede ser más fácil de entender que una implementación de Lisp / Haskell. (Pero, probablemente, no, para ser sincero. JavaScript no estaba pensado para este tipo de cosas.) </ ShamelessPlug>