En programación funcional , fold (también denominado reduce , recover , added , compress o inject ) 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 dada, recombinan los resultados del procesamiento recursivo de sus partes constituyentes, creando un valor de retorno. Por lo general, un fold 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 fold procede a combinar elementos de la jerarquía de la estructura de datos , utilizando la función de manera sistemática.
Los pliegues son en cierto sentido duales a los despliegues , que toman un valor semilla y aplican una función de manera correcursiva para decidir cómo construir progresivamente una estructura de datos correcursiva, mientras que un pliegue descompone esa estructura de manera recursiva, reemplazándola con los resultados de aplicar una función de combinación en cada nodo en sus valores terminales y los resultados recursivos ( catamorfismo , versus anamorfismo de los despliegues).
Los pliegues pueden considerarse como el reemplazo consistente de 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 a otra lista, creando lo que se llama un nodo cons ( ), resultante de la aplicación de una función (escrita como dos puntos en Haskell ). Se puede ver un pliegue en listas como el reemplazo del nil al final de la lista con un valor específico y el reemplazo de cada cons 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 identidad en las listas (una copia superficial en el lenguaje de Lisp ), ya que reemplazar cons por consy nil por nilno cambiará el resultado. El diagrama de pliegue izquierdo sugiere una forma fácil de invertir una lista, foldl (flip (:)) []. Tenga en cuenta que los parámetros de cons deben invertirse, porque el elemento a agregar ahora es el parámetro de la derecha 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 la composición de la función .
Esta forma de ver las cosas proporciona una ruta sencilla para diseñar funciones de tipo fold 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 las funciones proporcionadas, y cualquier valor constante del tipo con los valores proporcionados. Este tipo de función se conoce generalmente como catamorfismo .
El plegado de la lista [1,2,3,4,5]con el operador de adición 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 plegado como el reemplazo de las comas en la lista con la operación +, lo que da 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 los paréntesis, aunque la forma específica en que se calcula será diferente. En el caso general de las 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 a la derecha ), o bien combinando el resultado de combinar recursivamente todos los elementos excepto el último, con el último elemento (llamado pliegue a la izquierda ). Esto corresponde a un operador binario que es asociativo por la derecha o por la izquierda, en la terminología de Haskell o Prolog . Con un pliegue a la derecha, la suma estaría entre paréntesis como 1 + (2 + (3 + (4 + 5))), mientras que con un pliegue a 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 a la derecha, se utiliza cuando se llega al final de la lista, y en el caso de un pliegue a la izquierda es lo 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, lo que daría para el pliegue a la derecha y ((((0 + 1) + 2) + 3) + 4) + 5para el pliegue 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!.
El uso de un valor inicial es necesario cuando la función de combinación f es asimétrica en sus tipos (p. ej. 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, con el mismo tipo que el del resultado de f , para que sea posible una cadena lineal de aplicaciones. Si estará orientado a la izquierda o a 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 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 del resultado es el mismo que el tipo de los elementos de la lista, los paréntesis se pueden colocar de manera arbitraria creando así un árbol binario de subexpresiones anidadas, p. ej. ((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 operativos 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 operan de manera consistente para cada nodo de una lista , los pliegues tipo árbol están orientados a toda la lista y operan de manera consistente en todos los grupos de nodos.
A menudo se desea elegir el elemento de identidad de la operación f como el 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 en varios otros lenguajes, se denominan foldr1y foldl1, haciendo referencia el 1 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 operaciones binarias 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 pliegue general sobre listas no vacías" foldrnque transforma su último elemento, aplicándole una función de argumento adicional, en un valor del tipo del resultado antes de comenzar el pliegue en sí, y por lo tanto es capaz de utilizar operaciones binarias de tipo asimétrico como la regular foldrpara producir un resultado de tipo diferente al tipo de los elementos de la lista.
Usando Haskell como ejemplo, foldly foldrse puede 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 ) xs Si la lista está vacía, el resultado es el valor inicial. Si no, se dobla la cola de la lista utilizando 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 al resultado de plegar el resto.
Las listas se pueden plegar en forma de árbol, tanto para listas definidas 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 descontrolada 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 el ejemplo a continuación).
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 : pares f xs ) foldi1 f [ x ] = x foldi1 f ( x : xs ) = f x ( foldi1 f ( pares f xs )) En presencia de una evaluación lazy o no estricta , foldrdevolverá inmediatamente la aplicación de f a la cabeza de la lista y el caso recursivo de plegado sobre el resto de la lista. Por lo tanto, si f es capaz de 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 a la derecha 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 de manera eficiente como un bucle, pero no puede manejar listas infinitas en absoluto: recursivamente para siempre en un bucle infinito .head == foldr (\a b->a) (error "empty list")foldl
Una vez alcanzado el final de la lista, se construye una expresiónfoldl mediante aplicaciones de profundización izquierda anidadas f, que luego se presentan al invocador para que la evalúe. Si la función fhiciera referencia a su segundo argumento primero aquí, y fuera capaz de 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 foldrrecurse 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 foldlrecurse 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 (\a b->b) (error "empty list")
La inversión de una lista también es recursiva en la cola (se puede implementar usando ). En listas finitas , eso significa que el plegado por la izquierda y la inversión se pueden componer para realizar un plegado por la derecha de una manera recursiva en la cola (cf. ), con una modificación a la función para que invierta el orden de sus argumentos (es decir, ), construyendo de manera recursiva en la cola una representación de la expresión que construiría el plegado por la derecha. La estructura de lista intermedia extraña se puede eliminar con la técnica de estilo de paso de continuación , ; de manera similar, ( solo se necesita 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 combinar funciones para 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 los pliegues a la izquierda que utilizan evaluación diferida, el nuevo parámetro inicial no se evalúa antes de que se realice la llamada recursiva. Esto puede provocar desbordamientos de pila cuando se llega al final de la lista y se intenta evaluar la expresión potencialmente gigantesca resultante. Por esta razón, estos lenguajes a menudo proporcionan una variante más estricta del pliegue a la izquierda que fuerza la evaluación del parámetro inicial antes de realizar la llamada recursiva. En Haskell, esta es la foldl'función (nótese el apóstrofo, que se pronuncia 'prime') en la Data.Listbiblioteca (aunque hay que tener en cuenta el hecho de que forzar un valor creado con un constructor de datos diferido no forzará sus constituyentes automáticamente por sí mismo). Combinados con la recursión de cola, estos pliegues se acercan a la eficiencia de los bucles, lo que garantiza la operación en espacio constante, cuando la evaluación diferida 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" ( mapa mostrar [ 1 .. 13 ]) "(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0))))))))))))))" λ > foldl ( \ 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" ( 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 plegamiento 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 números primos se define de manera concisa como un plegado de la operación de diferencia 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 ordenación por fusión (y su variedad de eliminación de duplicados, nubsort) se podría definir fácilmente utilizando un plegado tipo árbol como
ordenación por fusión xs = combinación plegable [] [[ x ] | x <- xs ] ordenación por nub xs = unión plegable [] [[ x ] | x <- xs ] con la función mergeuna variante de preservación de duplicados de union.
Las funciones headpodrían lasthaberse definido a través del plegado como
cabeza = foldr ( \ x r -> x ) ( error "cabeza: Lista vacía" ) último = foldl ( \ a x -> x ) ( error "último: Lista vacía" ) El pliegue es una función polimórfica . Para cualquier g que tenga una definición
g [ ] = vg ( x : xs ) = fx ( gxs ) entonces g se puede expresar como [12]
g = pliegue f v Además, en un lenguaje perezoso con listas infinitas, se puede implementar un combinador de punto fijo a través de 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