En programación funcional , plegar (también denominado reducir , acumular , agregar , comprimir o inyectar ) se refiere a una familia de funciones de orden superior que analizan una estructura de datos recursiva y, mediante el uso de una operación de combinación determinada, recombinan los resultados del procesamiento recursivo de su partes constituyentes, generando un valor de retorno. Normalmente, un pliegue se presenta con una función de combinación, un nodo superior de una estructura de datos y posiblemente algunos valores predeterminados que se utilizarán en determinadas condiciones. Luego, el pliegue procede a combinar elementos de la jerarquía de la estructura de datos , utilizando la función de forma sistemática.
En cierto sentido, los pliegues son duales con los despliegues , que toman un valor inicial y aplican una función de forma correcursiva para decidir cómo construir progresivamente una estructura de datos correcursiva, 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 , versus anamorfismo de despliegues).
Se puede considerar que los pliegues reemplazan constantemente los componentes estructurales de una estructura de datos con funciones y valores. Las listas , por ejemplo, se construyen en muchos lenguajes funcionales a partir de dos primitivos: cualquier lista es una lista vacía, comúnmente llamada nil ( []), o se construye anteponiendo un elemento delante de otra lista, creando lo que se llama un nodo contras . ( ), resultante de la aplicación de una función (escrita como dos puntos en Haskell ). Se puede ver un pliegue en las listas como reemplazar el valor nulo al final de la lista con un valor específico y reemplazar cada contra con una función específica. Estos reemplazos se pueden ver como un diagrama: Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil)))))cons(:)
Hay otra forma de realizar la transformación estructural de manera consistente, con el orden de los dos enlaces de cada nodo invertido cuando se introducen en la función de combinación:
Estas imágenes ilustran visualmente el pliegue derecho e izquierdo de una lista. También resaltan el hecho de que foldr (:) []es la función de identidad en las listas (una copia superficial en el lenguaje Lisp ), ya que reemplazar cons por consy nil por nilno cambiará el resultado. El diagrama de pliegue izquierdo sugiere una manera fácil de invertir una lista foldl (flip (:)) []. Tenga en cuenta que los parámetros de contras 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 mapa de orden superior en términos de foldr, componiendo la función para actuar sobre los elementos con cons, como:
mapa f = foldr (( : ) . f ) [] donde el punto (.) es un operador que denota composición de funciones .
Esta forma de ver las cosas proporciona una ruta sencilla para diseñar funciones tipo pliegue en otros tipos y estructuras de datos algebraicos , como varios tipos de árboles. Se escribe una función que reemplaza recursivamente los constructores del tipo de datos con funciones proporcionadas y cualquier valor constante del tipo con valores proporcionados. Esta función se denomina generalmente catamorfismo .
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 aproximada, se puede pensar en este pliegue como reemplazar las comas en la lista con la operación +, dando 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 del paréntesis, aunque la forma concreta en la que se calcula será diferente. En el caso general de funciones binarias no asociativas, el orden en el 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: ya sea combinando el primer elemento con el resultado de combinar recursivamente el resto (llamado pliegue derecho ), o combinando el resultado de combinar recursivamente todos los elementos menos el último, con el último elemento (llamado pliegue izquierdo ). Esto corresponde a que un operador binario sea asociativo por la derecha o asociativo por la izquierda, en la terminología de Haskell o Prolog . Con un pliegue hacia la derecha, la suma estaría entre paréntesis como 1 + (2 + (3 + (4 + 5))), mientras que con un pliegue hacia la izquierda estaría entre 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 un pliegue por la derecha se usa cuando se llega al final de la lista, y en el caso de un pliegue por la izquierda es lo que se combina inicialmente con el primer elemento de la lista. En el ejemplo anterior, el valor 0 (la identidad aditiva ) se elegiría como valor inicial, dando 1 + (2 + (3 + (4 + (5 + 0))))para el pliegue derecho y ((((0 + 1) + 2) + 3) + 4) + 5para el pliegue izquierdo. 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!.
El uso de un valor inicial es necesario cuando la función combinadora 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 utilizar un valor inicial, del mismo tipo que el del resultado de f , para que sea posible una cadena lineal de aplicaciones. Si estará orientado hacia la izquierda o hacia la derecha estará determinado por los tipos esperados 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 se asocia a 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 se pueden colocar 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, el mismo para cualquier paréntesis, aunque los detalles operativos de cómo se calcula serán diferentes. Esto puede tener un impacto significativo en la eficiencia si f no es estricto .
Mientras que los pliegues lineales están orientados a nodos y operan de manera consistente para cada nodo de una lista , los pliegues en forma de árbol están orientados a toda la lista y operan de manera consistente en todos los grupos de nodos.
A menudo se quiere elegir el elemento identidad de la operación f como valor inicial z . Cuando ningún valor inicial parece apropiado, por ejemplo, cuando se quiere 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 primer elemento de la lista respectivamente como valor inicial. En Haskell y varios otros idiomas, estos se denominan foldr1y foldl1, 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 de tipo simétrico: los tipos tanto de sus argumentos como de su resultado deben ser los mismos. 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 resultado antes de comenzar el plegado en sí, y por lo tanto, puede utilizar una operación binaria de tipo asimétrico como la normal foldrpara producir un resultado de tipo diferente del tipo de elementos de la lista.
Usando Haskell como ejemplo, foldlse foldrpuede formular en algunas ecuaciones.
foldl :: ( b -> a -> b ) -> b -> [ a ] -> b foldl f z [] = z foldl f z ( x : xs ) = foldl f ( f z x ) xs Si la lista está vacía, el resultado es el valor inicial. Si no, dobla la cola de la lista usando como nuevo valor inicial el resultado de aplicar f al antiguo valor inicial y al primer elemento.
carpeta :: ( a -> b -> b ) -> b -> [ a ] -> b carpeta f z [] = z carpeta f z ( x : xs ) = f x ( carpeta f z xs ) Si la lista está vacía, el resultado es el valor inicial z. Si no, aplica f al primer elemento y al resultado de doblar el resto.
Las listas se pueden plegar en forma de á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 ( pares f xs ) foldi f z [] = z foldi f z ( x : xs ) = f x ( foldi f z ( pares f xs )) pares f ( x : y : t ) = f x y : pares f t pares _ t = t En el caso de foldiuna función, para evitar su evaluación desbocada en listas definidas indefinidamente , la función no siempref debe exigir el valor de su segundo argumento, al menos no todo, o no inmediatamente (ver ejemplo a continuación).
plegarl1 f [ x ] = x plegarl1 f ( x : y : xs ) = plegarl1 f ( f x y : xs ) pliegue1 f [ x ] = x pliegue1 f ( x : xs ) = f x ( pliegue1 f xs ) foldt1 f [ x ] = x foldt1 f ( x : y : xs ) = foldt1 f ( f x y : pares f xs ) foldi1 f [ x ] = x foldi1 f ( x : xs ) = f x ( foldi1 f ( pares fxs ) ) En presencia de evaluación diferida o no estricta , la aplicación de ffoldr se devolverá inmediatamente al encabezado de la lista y el caso recursivo de plegar el resto de la lista. Por lo tanto, si f es capaz de producir una 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 recursividad se detendrá (por ejemplo, ) . Esto permite que los pliegues derechos operen en listas infinitas. Por el contrario, se llamará a sí mismo inmediatamente con nuevos parámetros hasta llegar al final de la lista. Esta recursividad de cola se puede compilar eficientemente como un bucle, pero no puede manejar listas infinitas en absoluto: se repetirá para siempre en un bucle infinito .head == foldr (\a b->a) (error "empty list")foldl
Al llegar al final de la lista, se construye una expresiónfoldl mediante aplicaciones anidadas de profundización hacia la izquierda f, que luego se presenta a la persona que llama para que la evalúe. Si la función fhiciera referencia primero a su segundo argumento aquí y fuera capaz de producir una parte de su resultado sin hacer referencia al caso recursivo (aquí, a su izquierda , es decir, en su primer argumento), entonces la recursividad se detendría. Esto significa que, si bien foldrse repite a la derecha , permite una función de combinación diferida para inspeccionar los elementos de la lista desde la izquierda; y a la inversa, aunque foldlse repite a la izquierda , permite que una función de combinación diferida inspeccione los elementos de la lista desde la derecha, si así lo desea (por ejemplo, ).last == foldl (\a b->b) (error "empty list")
Invertir una lista también es recursivo al final (se puede implementar usando ). En listas finitas , eso significa que el pliegue a la izquierda y la inversión se pueden componer para realizar un pliegue a la derecha de forma recursiva (cf. ), con una modificación en la función para que invierta el orden de sus argumentos (es decir, ), construyendo recursivamente con la cola una representación de expresión que se construiría con el pliegue hacia la derecha. La estructura de lista intermedia superflua se puede eliminar con la técnica de estilo de paso continuo ; de manera similar, ( solo es necesario en lenguajes como Haskell con su orden invertido de argumentos para la función de combinación de diferencia, por ejemplo, en Scheme donde se usa el mismo orden de argumentos para combinar funciones para ambos y ).rev = foldl (\ys x -> x : ys) []1+>(2+>(3+>0)) == ((0<+3)<+2)<+1ffoldr f z == foldl (flip f) z . foldl (flip (:)) []foldr f z xs == foldl (\k x-> k . f x) id xs zfoldl f z xs == foldr (\x k-> k . flip f x) id xs zflipfoldlfoldlfoldr
Otro punto técnico es que, en el caso de pliegues a la izquierda que utilizan una evaluación diferida, el nuevo parámetro inicial no se evalúa antes de realizar la llamada recursiva. Esto puede provocar desbordamientos de pila cuando uno llega al final de la lista e intenta evaluar la expresión potencialmente gigantesca resultante. Por esta razón, dichos lenguajes suelen proporcionar una variante más estricta de plegado hacia la izquierda que obliga a la evaluación del parámetro inicial antes de realizar la llamada recursiva. En Haskell, esta es la foldl'función (tenga en cuenta el apóstrofe, pronunciado 'principal') en la Data.Listbiblioteca (aunque hay que tener en cuenta el hecho de que forzar un valor creado con un constructor de datos perezoso no forzará a sus constituyentes automáticamente por sí solo). Combinados con la recursividad de la cola, estos pliegues se acercan a la eficiencia de los bucles, asegurando una operación espacial constante, cuando la evaluación perezosa del resultado final es imposible o indeseable.
Usando 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)))))))))))))" λ > vecesl ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( mapa mostrar [ 1 .. 13 ]) "((((((((((((( (0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)" λ > foldt ( \ x y - > concat [ "(" , x , "+" , y , ")" ]) "0" ( mostrar mapa [ 1 .. 13 ]) "(((((1+2)+(3+4)) +((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)" λ > foldi ( \ x y -> concat [ " (" , x , "+" , y , ")" ]) "0" ( mostrar mapa [ 1 .. 13 ]) "(1+((2+3)+(((4+5)+(6 +7))+((((8+9)+(10+11))+(12+13))+0))))" El plegamiento infinito en forma de árbol se demuestra, por ejemplo, en la producción de números primos recursivos mediante el tamiz ilimitado 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 . gramo. gramo. gramo. ... donde la función unionopera en listas ordenadas de manera local para producir eficientemente su unión de conjuntos y minussu diferencia de conjuntos .
Un prefijo finito de números primos se define de manera concisa como una operación de plegado de diferencias de conjuntos sobre las listas de múltiplos enumerados de números enteros, como
primosTo n = foldl1 menos [[ 2 * x , 3 * x .. n ] | x <- [ 1 .. n ]] Para listas finitas, por ejemplo, la clasificación por fusión (y su variedad de eliminación de duplicados nubsort) podría definirse fácilmente utilizando el plegado en forma de árbol como
mergesort xs = foldt merge [] [[ x ] | x <- xs ] nubsort xs = unión plegable [] [[ x ] | x <- xs ] con la función mergeuna variante de preservación de duplicados union.
Funciones heady lastpodría 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" ) 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 se puede expresar como [12]
g = carpeta f v Además, en un lenguaje perezoso con listas infinitas, se puede implementar un combinador de punto fijo mediante pliegues, [13] lo que demuestra que las iteraciones se pueden reducir a pliegues:
y f = foldr ( \ _ -> f ) indefinido ( repetir indefinido ) functools.reduce: import functoolsreduce:from functools import reduce