En la 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 dada, recombinan los resultados del procesamiento recursivo de sus datos. partes constituyentes, creando un valor de retorno. Normalmente, un pliegue se presenta con una función de combinación , un nodo superior de una estructura de datosy 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 manera sistemática.
Los pliegues son, en cierto sentido, duales a los despliegues , que toman un valor semilla y aplican una función core cursivamente para decidir cómo construir progresivamente una estructura de datos corecursiva, mientras que un pliegue rompe recursivamente esa estructura, 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 despliegues).
Como transformaciones estructurales
Se puede considerar que los pliegues reemplazan consistentemente 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 primitivas: cualquier lista es una lista vacía, comúnmente llamada nil ( []
), o se construye prefijando un elemento delante de otra lista, creando lo que se llama un nodo de contras. ( ), resultante de la aplicación de una función (escrita como dos puntos en Haskell ). Uno puede ver un pliegue en las listas como reemplazar el cero 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 coherente, con el orden de los dos enlaces de cada nodo invertido cuando se alimenta a la función de combinación:
Estas imágenes ilustran visualmente el pliegue derecho e izquierdo de una lista . También destacan 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 con cons
y nil con nil
no cambiará el resultado. El diagrama del pliegue izquierdo sugiere una manera fácil de invertir una lista foldl (flip (:)) []
. Tenga en cuenta que los parámetros de los contras 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 simple para diseñar funciones similares a pliegues en otros tipos y estructuras de datos algebraicos , como varios tipos de árboles. Uno 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 .
En 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 aproximada, se puede pensar en este pliegue como si se reemplazaran las comas en la lista con la operación +, dando 1 + 2 + 3 + 4 + 5
.
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 específica en 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 a la derecha o asociativo a 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 usa cuando se llega al final de la lista, y en el caso de un pliegue a la izquierda es el que inicialmente se combina 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) + 5
para 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 de identidad para la multiplicación es 1. Esto nos daría el resultado 1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!
.
Pliegues lineales versus pliegues en forma de árbol
El uso de un valor inicial es necesario cuando la función de combinación f es asimétrica en sus tipos (p a → b → b
. Ej. ), 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 será 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 pueden ser colocados en forma arbitraria creando así un árbol de sub-expresiones anidadas, por ejemplo, ((1 + 2) + (3 + 4)) + 5
. Si la operación binaria f es asociativa este valor estará bien definido, es decir, igual 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 nodos y operan de manera consistente para cada nodo de una lista , los pliegues en forma de árbol están orientados a listas completas y operan de manera consistente en todos los grupos de nodos.
Pliegues especiales para listas no vacías
A menudo se desea elegir el elemento de identidad de la operación f como valor inicial z . Cuando ningún valor inicial parece apropiado, por ejemplo, cuando se quiere doblar 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, hay variantes de foldr
y foldl
que usan el último y primer elemento de la lista respectivamente como valor inicial. En Haskell y varios otros lenguajes, estos se denominan foldr1
y foldl1
, el 1 hace referencia a la provisión automática de un elemento inicial, y el 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 de tipo: los tipos de sus argumentos y su resultado deben ser los mismos. Richard Bird en su libro de 2010 propone [1] "una función de plegado general en listas no vacías" foldrn
que 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 usar una operación binaria asimétrica de tipo como la normal foldr
para producir un resultado de tipo diferente del tipo de elementos de la lista.
Implementación
Pliegues lineales
Usando Haskell como ejemplo, foldl
y foldr
se puede formular en algunas ecuaciones.
plieguel :: ( b -> a -> b ) -> b -> [ a ] -> b plieguel f z [] = z plieguel f z ( x : xs ) = plieguel f ( f z x ) xs
Si la lista está vacía, el resultado es el valor inicial. Si no es así, doble la cola de la lista usando como nuevo valor inicial el resultado de aplicar f al antiguo valor inicial y al primer elemento.
plieguer :: ( a -> b -> b ) -> b -> [ a ] -> b plieguer f z [] = z plieguer f z ( x : xs ) = f x ( plieguer f z xs )
Si la lista está vacía, el resultado es el valor inicial z. De lo contrario, aplique f al primer elemento y al resultado de doblar el resto.
Pliegues en forma de árbol
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 la foldi
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 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 : pares f xs ) foldi1 f [ x ] = x foldi1 f ( x : xs ) = f x ( foldi1 f ( pares f xs ))
Consideraciones de orden de evaluación
En presencia de una evaluación perezosa o no estricta , foldr
se devolverá inmediatamente la aplicación de f al encabezado de la lista y el caso recursivo de doblar el resto de la lista. Por lo tanto, si f es capaz de producir alguna parte de su resultado sin referencia al caso recursivo a su "derecha", es decir, en su segundo argumento, y el resto del resultado nunca se exige, entonces la recursividad se detendrá (p. Ej., ) . Esto permite que los pliegues 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 recursividad de cola se puede compilar eficientemente como un bucle, pero no puede tratar con listas infinitas en absoluto; se repetirá para siempre en un bucle infinito .head == foldr (\a b->a) (error "empty list")
foldl
Habiendo llegado al final de la lista, una expresión se construye en efecto mediante aplicaciones foldl
anidadas de profundización a la izquierda f
, que luego se presenta al llamador para que sea evaluada. Si la función se f
refiriera primero a su segundo argumento aquí, y pudiera producir alguna parte de su resultado sin hacer 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 se foldr
repite a la derecha , permite una función de combinación perezosa para inspeccionar los elementos de la lista desde la izquierda; ya la inversa, mientras se foldl
repite a la izquierda , permite que una función de combinación perezosa inspeccione los elementos de la lista desde la derecha, si así lo desea (p . ej., ).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 pliegue a la izquierda y el reverso se pueden componer para realizar un pliegue a la derecha de una manera recursiva de cola (cf. ), con una modificación a la función para que invierta el orden de sus argumentos (es decir, ), tail-recursivamente construyendo una representación de expresión que construiría el pliegue derecho. La estructura de lista intermedia extraña se puede eliminar con la técnica de estilo de continuación-pase ; de manera similar, ( solo se necesita en lenguajes como Haskell con su orden invertido de argumentos a la función de combinación de diferente, 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)<+1
f
foldr f z == foldl (flip f) z . foldl (flip (:)) []
foldr f z xs == foldl (\k x-> k . f x) id xs z
foldl f z xs == foldr (\x k-> k . flip f x) id xs z
flip
foldl
foldl
foldr
Otro punto técnico es que, en el caso de pliegues izquierdos que utilizan la 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 uno llega al final de la lista e intenta evaluar la expresión potencialmente gigantesca resultante. Por esta razón, dichos lenguajes a menudo proporcionan una variante más estricta de plegado a la izquierda que fuerza la evaluación del parámetro inicial antes de realizar la llamada recursiva. En Haskell, esta es la función foldl'
(tenga en cuenta el apóstrofe, pronunciado 'primo') en la Data.List
biblioteca (uno debe ser consciente del hecho de que forzar un valor construido con un constructor de datos perezoso no forzará a sus constituyentes automáticamente por sí mismo). Combinado con la recursividad de la cola, dichos pliegues se acercan a la eficiencia de los bucles, lo que garantiza una operación espacial constante, cuando la evaluación perezosa del resultado final es imposible o indeseable.
Ejemplos de
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 muestra [ 1 .. 13 ]) "(1+ (2+ (3 + (4+ (5+ (6+ (7+ (8+ (9+ (10+ (11+ (12+ (13 + 0))))))))))))) " λ > foldl ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( mapa muestra [ 1 .. 13 ]) "(((((((( (((((0 + 1) +2) +3) +4) +5) +6) +7) +8) +9) +10) +11) +12) +13) " λ > foldt ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( mapa muestra [ 1 .. 13 ]) "(((((1 + 2 ) + (3 + 4)) + ((5 + 6) + (7 + 8))) + (((9 + 10) + (11 + 12)) + 13)) + 0) " λ > foldi ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( mapa muestra [ 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 de primos recursivos mediante un tamiz ilimitado de Eratóstenes en Haskell :
primos = 2 : _A (( 3 : ) . minus [ 5 , 7 .. ] . Foldi ( \ ( x : xs ) ys -> x : unión xs ys ) [] . mapa ( \ p -> [ p * p , p * p + 2 * p .. ])) _Y g = g ( _Y g ) - = g. g. g. g. ...
donde la función unionopera en listas ordenadas de una manera local para producir eficientemente su unión de conjuntos y minussu diferencia de conjuntos .
Para listas finitas, por ejemplo, la ordenació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 de pliegue [] [[ x ] | x <- xs ]
con la función mergeuna variante de preservación de duplicados union
.
Funciones head
y last
podrí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" )
En varios idiomas
Idioma | Pliegue izquierdo | Pliegue derecho | Pliegue izquierdo sin valor inicial | Pliegue derecho sin valor inicial | Desplegar | Notas | |
---|---|---|---|---|---|---|---|
APL | func⍨/⌽initval,vector | func/vector,initval | func⍨/⌽vector | func/vector | |||
C # 3.0 | ienum | ienum.Reverse() | ienum | ienum.Reverse() | Aggregate es un método de extensión ienum es IEnumerable similar en todos los lenguajes .NET | ||
C ++ | std::accumulate( | std::accumulate( | en el encabezado
begin , end , rbegin , rend son iteradores func puede ser un puntero de función o un objeto de función | ||||
C ++ 17 | (initval op ... op pack) | (pack op ... op initval) | (... op pack) | (pack op ...) | Fold expression (solo para plantillas de función variadic): op es un operador binario (ambas op s deben ser iguales, p. Ej., (std::cout << ... << args) ), Pack es un paquete de parámetros no expandido. | ||
CFML | obj.reduce(func,initial) | obj.reduce(func) | Donde func recibe como argumentos el resultado de la operación anterior (o el initial valor en la primera iteración); el artículo actual; el índice o la clave del elemento actual; y una referencia a laobj | ||||
Clojure | (reduce func initval list) | (reduce func initval (reverse list')) | (reduce func list) | (reduce func" (reverse list)) | Véase también clojure.core.reducers / fold | ||
Lisp común | (reduce func list :initial-value initval) | (reduce func list :from-end t :initial-value initval) | (reduce func list) | (reduce func list :from-end t) | |||
Rizo | {{TreeNode.default treeNode ...} .to-Iterator} | {{TreeNode.default treeNode ...} .reverse} | {for {treeNode | {for {{treeNode.reverse} | también implementan DefaultListModel y HashTable to-Iterator | ||
D | reduce!func(initval, list) | reduce!func(initval, list | reduce!func(list) | reduce!func( | en módulo std.algorithm | ||
Elixir | List.foldl(list, acc, fun) | List.foldr(list, acc, fun) | Ver documentación para ejemplos de uso | ||||
Olmo | List.foldl(Fun, Accumulator, List) | List.foldr(Fun, Accumulator, List) | Consulte también List API [1] | ||||
Erlang | lists:foldl(Fun, Accumulator, List) | lists:foldr(Fun, Accumulator, List) | |||||
F# | Seq/List.fold func initval list | List.foldBack func list initval | Seq/List.reduce func list | List.reduceBack func list | Seq.unfold func initval | ||
Gosu | Iterable.fold(f(agg, e)) | Todos son métodos de extensión en la interfaz iterable de Java, también se admiten matrices | |||||
Groovy | list | list.reverse() | list | list.reverse() | |||
Haskell | foldl func initval list | foldr func initval list | foldl1 func list | foldr1 func list | unfoldr func initval | Para foldl, la función de plegado toma argumentos en el orden opuesto al de foldr. | |
Haxe | Lambda.fold(iterable, func, initval) | ||||||
J | verb~/|. initval,array | verb/ array,initval | verb~/|. array | verb/ array | u / y aplica la díada u entre los elementos de y. "Diccionario J: Insertar" | ||
Java 8+ | stream.reduce | stream.reduce | |||||
JavaScript 1.8 ECMAScript 5 | array.reduce | array.reduce | |||||
Julia | foldl(op, itr; [init]) | foldr(op, itr; [init]) | foldl(op, itr) | foldr(op, itr) | |||
Kotlin | Iterable.fold | Iterable.foldRight | Iterable.reduce(func) | Iterable .reduceRight(func) | Otras colecciones también admiten fold [2] y reduce . [3] También hay Result.fold(onSuccess, onFailure) , [4] que reduce a Result (éxito o fracaso) al tipo de retorno de onSuccess y onFailure . | ||
LFE | (lists:foldl func accum list) | (lists:foldr func accum list) | |||||
Logtalk | fold_left(Closure, Initial, List, Result) | fold_right(Closure, Initial, List, Result) | Meta-predicados proporcionados por el meta objeto de la librería estándar. También se pueden usar las abreviaturas foldl y foldr . | ||||
Arce | foldl(func, initval, sequence) | foldr(func, initval, sequence) | |||||
Mathematica | Fold[func, initval, list] | Fold[func, initval, Reverse[list]] | Fold[func, list] | Fold[func, Reverse[list]] | NestWhileList[func,, initval, predicate] | Fold sin un valor inicial es compatible con las versiones 10.0 y superiores. | |
MATLAB | fold(@func, list, defaultVal) | fold(@func, flip(list), defaultVal) | fold(@func, list) | fold(@func, flip(list)) | | Requiere Caja de herramientas de matemáticas simbólicas, compatible con R2016b. | |
Maxima | lreduce(func, list, initval) | rreduce(func, list, initval) | lreduce(func, list) | rreduce(func, list) | |||
Mythryl | fold_left func initval list | fold_right func initval list | La función proporcionada toma sus argumentos en una tupla. | ||||
OCaml | List.fold_left func initval list | List.fold_right func list initval | Base.Sequence.unfold ~init ~f [5] | ||||
Onz | {FoldL List Func InitVal} | {FoldR List Func InitVal} | |||||
PARI / GP | fold( f, A ) | ||||||
Perl | reduce block initval, list | reduce block list | en List::Util módulo | ||||
PHP | array_reduce(array, func, initval) | array_reduce( | array_reduce(array, func) | array_reduce( | Cuando no se proporciona initval , se usa NULL, por lo que no es un verdadero foldl1. Antes de PHP 5.3, initval solo puede ser un número entero. "func" es una devolución de llamada . Pruebe array_reduce en línea. | ||
Python 2.x | reduce(func, list, initval) | reduce(lambda x,y: func(y,x), reversed(list), initval) | reduce(func, list) | reduce(lambda x,y: func(y,x), reversed(list)) | |||
Python 3.x | functools.reduce(func, list, initval) | functools.reduce(lambda x,y: func(y,x), reversed(list), initval) | functools.reduce(func, list) | functools.reduce(lambda x,y: func(y,x), reversed(list)) | En módulo functools . [6] | ||
R | Reduce(func, list, initval) | Reduce(func, list, initval, right=TRUE) | Reduce(func, list) | Reduce(func, list, right=TRUE) | R admite el plegado a la derecha y el plegado a la izquierda o la derecha con o sin un valor inicial a través de los argumentos right e init para la función Reducir. | ||
Rubí | enum | enum.reverse_each | enum | enum.reverse_each | En Ruby 1.8.7+, también puede pasar un símbolo que representa una función en lugar de un bloque. enum es una enumeración. Tenga en cuenta que estas implementaciones de pliegues correctos son incorrectas para el bloque & no conmutativo (también el valor inicial se coloca en el lado incorrecto). | ||
Oxido | iterator.fold(initval, func) | iterator.rev().fold(initval, func) | iterator.rev() requiere iterator ser un DoubleEndedIterator . [7] | ||||
Scala | list.foldLeft(initval)(func) (initval /: list)(func) | list.foldRight(initval)(func) (list :\ initval)(func) | list.reduceLeft(func) | list.reduceRight(func) | La sintaxis de pliegue simbólico de Scala tenía la intención de parecerse al árbol inclinado hacia la izquierda o hacia la derecha que se usa comúnmente para explicar la operación de pliegue, [8] pero desde entonces ha sido reinterpretado como una ilustración de un dominó que se cae. [9] Los dos puntos provienen de un mecanismo de sintaxis general de Scala mediante el cual el operador infijo aparente se invoca como un método en el operando izquierdo con el operando derecho pasado como argumento, o viceversa si el último carácter del operador son dos puntos, aquí aplicado simétricamente . Scala también presenta los pliegues en forma de árbol usando el método | ||
Esquema R 6 RS | (fold-left func initval list) | (fold-right func initval list) | (reduce-left func defaultval list) | (reduce-right func defaultval list) | srfi / 1 srfi / 43 | ||
Charla | aCollection inject: aValue into: aBlock | aCollection reduce: aBlock | ANSI Smalltalk no define #reduce: pero muchas implementaciones lo hacen. | ||||
ML estándar | foldl func initval list | foldr func initval list | La función proporcionada toma sus argumentos en una tupla. Para foldl, la función de plegado toma argumentos en el mismo orden que para foldr. | ||||
Rápido | array.reduce(initval, func) | array.reverse() | |||||
XPath 3.1 | array:fold-left(
| array:fold-right(
| En XPath 3.1, debido a razones históricas, los tipos array y sequence son incompatibles, de ahí la necesidad de fold funciones separadas para array y parasequence
| ||||
Xtend | iterable.fold(initval,[func]) | iterable.reduce[func] |
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 se puede expresar como [11]
g = plieguer f v
Además, en un lenguaje perezoso con listas infinitas, se puede implementar un combinador de punto fijo mediante pliegue, [12] demostrando que las iteraciones se pueden reducir a pliegues:
y f = foldr ( \ _ -> f ) indefinido ( repetir indefinido )
Ver también
- Función agregada
- Operación binaria iterada
- Catamorfismo , una generalización del pliegue
- Homomorfismo
- Mapa (función de orden superior)
- Suma de prefijo
- Tipo de datos recursivos
- Operador de reducción
- Recursividad estructural
Referencias
- ^ Richard Bird, "Perlas de diseño de algoritmos funcionales", Cambridge University Press 2010, ISBN 978-0-521-51338-8 , p. 42
- ^ "pliegue - Lenguaje de programación Kotlin" . Kotlin . Jetbrains . Consultado el 29 de marzo de 2019 .
- ^ "reducir - 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 .
- ^ "Base" . Jane Street Capital . Consultado el 26 de febrero de 2019 .
- ^ Para referencia
functools.reduce
:import functools
Para referenciareduce
:from functools import reduce
- ^ "Iterador en core :: iter" . Óxido . Equipo 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 . Consultado el 14 de octubre de 2013 .
- ^ Sterling, Nicholas. "Una sensación intuitiva para el operador /: de Scala (foldLeft)" . Consultado 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. "Un tutorial sobre la universalidad y expresividad del pliegue" (PDF) . Revista de programación funcional (9 (4)): 355–372 . Consultado el 26 de marzo de 2009 .
- ^ Papa, Bernie. "Obtener una solución desde el lado derecho" (PDF) . The Monad.Reader (6): 5–16 . Consultado el 1 de mayo de 2011 .
enlaces externos
- "Funciones de orden superior: mapear, plegar y filtrar"
- "Unidad 6: Funciones de plegado de orden superior"
- "Doblar en Tcl"
- "Construcción de homomorfismo de lista a partir de pliegues izquierdo y derecho"
- "El plegador mágico"