Hispanopedia WikiEn programación funcional , una operación de plegado es una función de orden superior que analiza una estructura de datos recursiva y, mediante una operación de combinación específica, recombina los resultados del procesamiento recursivo de sus partes constituyentes, generando un valor de retorno. También se la conoce como operación de reducción , acumulación , agregación , compresión o inyección . Normalmente, a una operación de plegado se le presenta una función de combinación, un nodo superior de la estructura de datos y, posiblemente, algunos valores predeterminados que se utilizarán bajo ciertas condiciones. A continuación, la operación de plegado combina los elementos de la jerarquía de la estructura de datos , utilizando la función de forma sistemática.
Los pliegues son, en cierto sentido, duales a los despliegues , que toman un valor semilla y aplican una función de forma corecursiva para decidir cómo construir progresivamente una estructura de datos corecursiva, mientras que un pliegue descompone recursivamente esa estructura, reemplazándola con los resultados de aplicar una función de combinación en cada nodo sobre sus valores terminales y los resultados recursivos ( catamorfismo , en contraposición al anamorfismo de los despliegues).
Como transformaciones estructurales
Las reestructuraciones pueden considerarse como la sustitución sistemática de los componentes estructurales de una estructura de datos por funciones y valores. Las listas , por ejemplo, se construyen en muchos lenguajes funcionales a partir de dos primitivas: cualquier lista es una lista vacía, comúnmente llamada nil ( []), o se construye anteponiendo un elemento a otra lista, creando lo que se denomina un nodo cons ( ), resultado de la aplicación de una función (escrito con dos puntos en Haskell ). Una reestructuración en listas puede verse como la sustitución del nil al final de la lista por un valor específico y la sustitución de cada cons por una función específica. Estas sustituciones pueden representarse mediante un diagrama: Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) cons(:)
Existe otra forma de realizar la transformación estructural de manera consistente, invirtiendo el orden de los dos enlaces de cada nodo al introducirlos en la función de combinación:
Estas imágenes ilustran visualmente el plegado derecho e izquierdo de una lista . También resaltan el hecho de que foldr (:) []es la función identidad en listas (una copia superficial en la jerga de Lisp ), ya que reemplazar `cons` con ` nil` consy `nil` con `nil` nilno cambiará el resultado. El diagrama de plegado izquierdo sugiere una manera sencilla de invertir una lista, ` foldl (flip (:)) []. Nótese que los parámetros de `cons` deben invertirse, porque el elemento a agregar ahora es el parámetro derecho de la función de combinación. Otro resultado fácil de ver desde este punto de vista es escribir la función de mapeo de orden superior en términos de foldr`,` componiendo la función para actuar sobre los elementos con ` cons,` como:
map f = foldr (( : ) . f ) []donde el punto (.) es un operador que denota la composición de funciones .
Esta perspectiva ofrece una vía sencilla para diseñar funciones de tipo plegado en otros tipos de datos y estructuras algebraicas, como distintos tipos de árboles. Se escribe una función que reemplaza recursivamente los constructores del tipo de dato con funciones proporcionadas, así como cualquier valor constante del tipo con valores proporcionados. A esta función se la suele denominar catamorfismo .
En las listas
El plegado de la lista [1,2,3,4,5]con el operador de suma daría como resultado 15, la suma de los elementos de la lista [1,2,3,4,5]. En una aproximación burda, se puede pensar en este plegado como reemplazar las comas en la lista con la operación +, dando como resultado 1 + 2 + 3 + 4 + 5. [ 1 ]
En el ejemplo anterior, + es una operación asociativa , por lo que el resultado final será el mismo independientemente de la paréntesis, aunque la forma específica en que se calcula será diferente. En el caso general de funciones binarias no asociativas, el orden en que se combinan los elementos puede influir en el valor del resultado final. En las listas, hay dos formas obvias de llevar a cabo esto: o bien combinando el primer elemento con el resultado de combinar recursivamente el resto (llamado pliegue derecho ), o bien combinando el resultado de combinar recursivamente todos los elementos excepto el último, con el último elemento (llamado pliegue izquierdo ). Esto corresponde a que un operador binario sea asociativo derecho o asociativo izquierdo, en la terminología de Haskell o Prolog . Con un pliegue derecho, la suma se paréntesis como 1 + (2 + (3 + (4 + 5))), mientras que con un pliegue izquierdo se paréntesis como (((1 + 2) + 3) + 4) + 5.
En la práctica, es conveniente y natural tener un valor inicial que, en el caso de una reducción a la derecha, se usa al llegar al final de la lista, y en el caso de una reducción a la izquierda, es el que se combina inicialmente con el primer elemento de la lista. En el ejemplo anterior, se elegiría el valor 0 (la identidad aditiva1 + (2 + (3 + (4 + (5 + 0)))) ) como valor inicial, dando para la reducción a la derecha y ((((0 + 1) + 2) + 3) + 4) + 5para la reducción a la izquierda. Para la multiplicación, una elección inicial de 0 no funcionaría: 0 * 1 * 2 * 3 * 4 * 5 = 0. El elemento identidad para la multiplicación es 1. Esto nos daría el resultado 1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!.
Pliegues lineales frente a pliegues arborescentes
El uso de un valor inicial es necesario cuando la función de combinación f es asimétrica en sus tipos (por ejemplo, a → b → b), es decir, cuando el tipo de su resultado es diferente del tipo de los elementos de la lista. Entonces se debe usar un valor inicial, con el mismo tipo que el del resultado de f , para que sea posible una cadena lineal de aplicaciones. Si será orientado hacia la izquierda o hacia la derecha estará determinado por los tipos que espera de sus argumentos por la función de combinación. Si es el segundo argumento el que debe ser del mismo tipo que el resultado, entonces f podría verse como una operación binaria que asocia por la derecha , y viceversa.
Cuando la función es un magma , es decir simétrica en sus tipos ( a → a → a), y el tipo de resultado es el mismo que el tipo de los elementos de la lista, los paréntesis pueden colocarse de forma arbitraria, creando así un árbol binario de subexpresiones anidadas, por ejemplo, ((1 + 2) + (3 + 4)) + 5. Si la operación binaria f es asociativa, este valor estará bien definido, es decir, será el mismo para cualquier paréntesis, aunque los detalles operacionales de cómo se calcula serán diferentes. Esto puede tener un impacto significativo en la eficiencia si f no es estricta .
Mientras que los pliegues lineales están orientados a los nodos y funcionan de manera consistente para cada nodo de una lista , los pliegues en forma de árbol están orientados a la lista completa y funcionan de manera consistente en grupos de nodos.
Pliegues especiales para listas no vacías
A menudo se desea elegir el elemento neutro de la operación f como valor inicial z . Cuando ningún valor inicial parece apropiado, por ejemplo, cuando se desea plegar la función que calcula el máximo de sus dos parámetros sobre una lista no vacía para obtener el elemento máximo de la lista, existen variantes de foldry foldlque utilizan el último y el primer elemento de la lista respectivamente como valor inicial. En Haskell y otros lenguajes, estas se denominan foldr1y foldl1, donde el 1 hace referencia a la provisión automática de un elemento inicial y al hecho de que las listas a las que se aplican deben tener al menos un elemento.
Estos pliegues utilizan una operación binaria simétrica en cuanto al tipo: los tipos de sus argumentos y de su resultado deben ser iguales. Richard Bird, en su libro de 2010, propone [ 2 ] "una función de plegado general en listas no vacías" foldrnque transforma su último elemento, aplicándole una función de argumento adicional, en un valor del tipo de resultado antes de comenzar el plegado en sí, y por lo tanto puede utilizar una operación binaria asimétrica en cuanto al tipo como la regular foldrpara producir un resultado de un tipo diferente al tipo de los elementos de la lista.
Implementación
Pliegues lineales
Usando Haskell como ejemplo, foldlse foldrpuede formular en unas pocas ecuaciones.
foldl :: ( b -> a -> b ) -> b -> [ a ] -> b foldl f z [] = z foldl f z ( x : xs ) = foldl f ( f z x ) xsSi la lista está vacía, el resultado es el valor inicial. Si no, se pliega la cola de la lista usando como nuevo valor inicial el resultado de aplicar f al valor inicial anterior y al primer elemento.
foldr :: ( a -> b -> b ) -> b -> [ a ] -> b foldr f z [] = z foldr f z ( x : xs ) = f x ( foldr f z xs )Si la lista está vacía, el resultado es el valor inicial z. Si no, se aplica f al primer elemento y el resultado de plegar el resto.
Pliegues con forma de árbol
Las listas se pueden plegar de forma similar a un árbol, tanto para listas finitas como para listas definidas indefinidamente:
foldt f z [] = z foldt f z [ x ] = f x z foldt f z xs = foldt f z ( pairs f xs ) foldi f z [] = z foldi f z ( x : xs ) = f x ( foldi f z ( pairs f xs )) pairs f ( x : y : t ) = f x y : pairs f t pairs _ t = tEn el caso de foldiuna función, para evitar su evaluación descontrolada en listas definidas indefinidamente , la función fno siempre debe exigir el valor de su segundo argumento, al menos no todo el valor, o no inmediatamente (ver el ejemplo a continuación).
Pliegues para listas no vacías
foldl1 f [ x ] = x foldl1 f ( x : y : xs ) = foldl1 f ( f x y : xs )foldr1 f [ x ] = x foldr1 f ( x : xs ) = f x ( foldr1 f xs )foldt1 f [ x ] = x foldt1 f ( x : y : xs ) = foldt1 f ( f x y : pairs f xs ) foldi1 f [ x ] = x foldi1 f ( x : xs ) = f x ( foldi1 f ( pairs f xs ))Consideraciones sobre el orden de evaluación
En presencia de evaluación perezosa o no estrictafoldr , devolverá inmediatamente la aplicación de f al inicio de la lista y el caso recursivo de plegado sobre el resto de la lista. Por lo tanto, si f puede producir alguna parte de su resultado sin referencia al caso recursivo en su "derecha", es decir, en su segundo argumento, y el resto del resultado nunca se exige, entonces la recursión se detendrá (por ejemplo, ). Esto permite que los plegados derechos operen en listas infinitas. Por el contrario, se llamará inmediatamente a sí mismo con nuevos parámetros hasta que llegue al final de la lista. Esta recursión de cola se puede compilar eficientemente como un bucle, pero no puede manejar listas infinitas en absoluto: recurrirá para siempre en un bucle infinito .head==foldr(\ab->a)(error"empty list")foldl
Habiendo llegado al final de la lista, se construye una expresiónfoldl mediante aplicaciones anidadas de profundización izquierda f, que luego se presenta al llamador para su evaluación. Si la función fse refiriera primero a su segundo argumento aquí, y pudiera producir alguna parte de su resultado sin referencia al caso recursivo (aquí, a su izquierda , es decir, en su primer argumento), entonces la recursión se detendría. Esto significa que mientras foldrrecurre a la derecha , permite que una función de combinación perezosa inspeccione los elementos de la lista desde la izquierda; y a la inversa, mientras foldlrecurre a la izquierda , permite que una función de combinación perezosa inspeccione los elementos de la lista desde la derecha, si así lo elige (por ejemplo, ).last==foldl(\ab->b)(error"empty list")
Invertir una lista también es recursivo de cola (se puede implementar usando ). En listas finitas , eso significa que left-fold y reverse se pueden componer para realizar un right fold de forma recursiva de cola (cf. ), con una modificación a la función para que invierta el orden de sus argumentos (es decir, ), construyendo recursivamente de cola una representación de la expresión que right-fold construiría. La estructura de lista intermedia extranea se puede eliminar con la técnica de estilo de paso de continuación , ; de manera similar, ( solo es necesario en lenguajes como Haskell con su orden invertido de argumentos para la función de combinación de a diferencia de, por ejemplo, en Scheme donde se usa el mismo orden de argumentos para las funciones de combinación tanto para como para ).rev=foldl(\ysx->x:ys)[]1+>(2+>(3+>0))==((0<+3)<+2)<+1ffoldrfz==foldl(flipf)z.foldl(flip(:))[]foldrfzxs==foldl(\kx->k.fx)idxszfoldlfzxs==foldr(\xk->k.flipfx)idxszflipfoldlfoldlfoldr
Otro aspecto técnico es que, en el caso de las reducciones a la izquierda con evaluación perezosa, el nuevo parámetro inicial no se evalúa antes de la llamada recursiva. Esto puede provocar desbordamientos de pila al llegar al final de la lista e intentar evaluar la expresión resultante, que puede ser gigantesca. Por este motivo, estos lenguajes suelen ofrecer una variante más estricta de reducción a la izquierda que fuerza la evaluación del parámetro inicial antes de la llamada recursiva. En Haskell, esta función foldl'(nótese el apóstrofo, pronunciado «prime») se encuentra en la Data.Listbiblioteca (aunque hay que tener en cuenta que forzar un valor construido con un constructor de datos perezoso no forzará automáticamente sus componentes). Combinadas con la recursión de cola, estas reducciones se aproximan a la eficiencia de los bucles, garantizando un funcionamiento con espacio constante cuando la evaluación perezosa del resultado final es imposible o indeseable.
Ejemplos
Utilizando un intérprete de Haskell , las transformaciones estructurales que realizan las funciones de plegado se pueden ilustrar construyendo una cadena:
λ > foldr ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))" λ > foldl ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)" λ > foldt ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( mapa mostrar [ 1 .. 13 ]) "(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)" λ > foldi ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( mapa mostrar [ 1 .. 13 ]) "(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"El plegado infinito en forma de árbol se demuestra, por ejemplo, en la producción recursiva de primos mediante la criba ilimitada de Eratóstenes en Haskell :
primos = 2 : _Y (( 3 : ) . menos [ 5 , 7 .. ] . foldi ( \ ( x : xs ) ys -> x : unión xs ys ) [] . map ( \ p -> [ p * p , p * p + 2 * p .. ])) _Y g = g ( _Y g ) -- = g . g . g . g . ...donde la función unionopera sobre listas ordenadas de manera local para producir eficientemente su unión de conjuntos y minussu diferencia de conjuntos .
Un prefijo finito de primos se define concisamente como un plegado de la operación de diferencia de conjuntos sobre las listas de múltiplos enumerados de enteros, como
primosA n = foldl1 menos [[ 2 * x , 3 * x .. n ] | x <- [ 1 .. n ]]Para listas finitas, por ejemplo, la ordenación por fusión (y su variante que elimina duplicados nubsort) podría definirse fácilmente utilizando un plegado tipo árbol como
mergesort xs = foldt merge [] [[ x ] | x <- xs ] nubsort xs = foldt union [] [[ x ] | x <- xs ]con la función mergeuna variante que conserva los duplicados de union.
Las funciones heady lastpodrían haberse definido mediante el plegado como
head = foldr ( \ x r -> x ) ( error "head: Lista vacía" ) last = foldl ( \ a x -> x ) ( error "last: Lista vacía" )En varios idiomas
Universalidad
Fold es una función polimórfica . Para cualquier g que tenga una definición
g [] = v g ( x : xs ) = f x ( g xs )entonces g puede expresarse como [ 12 ]
g = pliegue f vAdemás, en un lenguaje perezoso con listas infinitas, se puede implementar un combinador de punto fijo mediante fold, [ 13 ] demostrando que las iteraciones se pueden reducir a folds:
y f = foldr ( \ _ -> f ) indefinido ( repetir indefinido )Véase también
Referencias
- ↑ "Unidad 6 de Haskell: Las funciones de plegado de orden superior | Antoni Diller" . www.cantab.net . Consultado el 4 de abril de 2023 .
- ↑ Richard Bird, "Perlas del diseño de algoritmos funcionales", Cambridge University Press 2010, ISBN 978-0-521-51338-8pág. 42
- ↑ "Array.prototype.reduce() - JavaScript | MDN" . developer.mozilla.org . 2023-12-11 . Consultado el 2024-01-16 .
- ↑ "fold - Lenguaje de programación Kotlin" . Kotlin . Jetbrains . Consultado el 29 de marzo de 2019 .
- ↑ "reduce - Lenguaje de programación Kotlin" . Kotlin . Jetbrains . Consultado el 29 de marzo de 2019 .
- ↑ "Resultado - Lenguaje de programación Kotlin" . Kotlin . Jetbrains . Consultado el 29 de marzo de 2019 .
- ↑ Para referencia
functools.reduce:import functoolsPara referenciareduce:from functools import reduce - ↑ "Iterador en core::iter" . Rust . Equipo de Rust . Consultado el 22 de junio de 2021 .
- ↑ Odersky, Martin (5 de enero de 2008). "Re: Blog: Mi veredicto sobre el lenguaje Scala" . Grupo de noticias : comp.scala.lang . Archivado del original el 14 de mayo de 2015. Recuperado el 14 de octubre de 2013 .
- ↑ Sterling, Nicholas (28 de julio de 2010). "Una sensación intuitiva para el operador /: de Scala (foldLeft)" . Recuperado el 24 de junio de 2016 .
- ↑ "Fold API - Biblioteca estándar de Scala" . www.scala-lang.org . Consultado el 10 de abril de 2018 .
- ↑ Hutton, Graham (1999). "Un tutorial sobre la universalidad y expresividad de fold" (PDF) . Journal of Functional Programming . 9 (4): 355– 372. doi : 10.1017/S0956796899003500 . Recuperado el 26 de marzo de 2009 .
- ↑ Pope, Bernie. "Getting a Fix from the Right Fold" (PDF) . The Monad.Reader (6): 5–16 . Recuperado el 1 de mayo de 2011 .
Enlaces externos
- "Funciones de orden superior: mapeo, plegado y filtrado"
- "Unidad 6: Las funciones de plegado de orden superior"
- "Plegado en Tcl"
- "Construcción de homomorfismos de listas a partir de pliegues izquierdos y derechos" Archivado el 13 de abril de 2009 en la Wayback Machine.
- "El plegado mágico"
- Funciones de orden superior
- Recursión
- Comparación de lenguajes de programación
- Iteración en programación
