Resumen de lista

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 29 de mayo de 2021; la verificación requiere 1 edición .

El plegamiento de listas ( plegamiento en inglés  , también conocido como reducir , acumular ) en programación  es una función de orden superior que convierte una estructura de datos en un solo valor atómico usando una función dada. La operación de plegado se usa a menudo en la programación funcional cuando se procesan listas . El plegamiento se puede generalizar a un tipo de datos algebraico arbitrario utilizando la noción de catamorfismo de la teoría de categorías .

Una función de resumen generalmente toma tres argumentos: una función de combinación f, un valor inicial starty una estructura de datos seq(una lista, en su forma más simple). Dependiendo de las propiedades de la función de combinación, puede haber diferentes implementaciones y diferentes estrategias para calcular . A veces, la función de resumen no toma un valor inicial, sino que requiere una lista no vacía; pero en muchos casos puede ser deseable especificar un valor inicial distinto de cero, que se utilizará la primera vez que se aplique la función de combinación. El uso de un valor inicial es necesario cuando el tipo de resultado de la función de combinación es diferente del tipo de los elementos de la lista, en cuyo caso el valor inicial debe ser del mismo tipo que el tipo de resultado.

Asociatividad

Para plegar por una operación asociativa , el orden de cálculo no afecta el resultado, por ejemplo, calcular la suma de los números de la lista (1 2 3 4 5), es decir, su plegamiento por la suma, se puede hacer en cualquier orden: o o , lo que permite le permite calcular el plegamiento de diferentes partes de la lista al mismo tiempo, es decir, paralelizar el plegamiento de la lista de cálculo en sistemas multiprocesador y de clúster.

Para operaciones no asociativas, el orden importa, por lo tanto, en el caso general, para el plegado, se requiere especificar el orden de los cálculos, en relación con esto, plegado a la derecha ( asociativo a la derecha ) y plegado a la izquierda ( asociativo por la izquierda ) se distinguen. Por ejemplo, para una lista , la función de pliegue asociativo izquierdo evaluará el valor de la expresión: seq := (elem_1 elem_2 ... elem_n)

(f ... (f (f start elem_1) elem_2) ... elem_n)

y asociativa derecha:

(f elem_1 (f elem_2 ... (f elem_n start) ... )).

Ejemplos

El factorial n se puede representar como una lista de números del 2 al n doblados usando la operación de multiplicación (por ejemplo, en lenguaje Haskell ):

fac n = foldl ( * ) 1 [ 2 .. n ]

Aquí:

fac - declaración de la función factorial
n - parámetro de entrada
después del signo =(igual) viene la definición de la función
foldl - función de convolución
1 — valor inicial para la convolución
[2..n] - se especifica una lista por la cual doblar - números del 2 al n

Un ejemplo de una función similar en Scala :

def fac ( n : BigInt ) = ( BigInt ( 2 ) a n ). doblar a la izquierda ( Entero grande ( 1 ))( _ * _ )

Literatura