Lista de diferencias

En informática , el término lista de diferencias se refiere a una estructura de datos que representa una lista con una operación de concatenación eficiente de complejidad O(1) y su conversión a una lista enlazada en un tiempo proporcional a su longitud. Las listas de diferencias pueden implementarse mediante funciones de primera clase o mediante unificación. La eficiencia de una lista de diferencias con respecto a otras representaciones de listas depende de los patrones de uso. Si un algoritmo construye una lista concatenando listas más pequeñas, que a su vez se construyen concatenando listas aún más pequeñas, entonces el uso de listas de diferencias puede mejorar el rendimiento al "aplanar" de forma efectiva los cálculos de construcción de la lista.

Una lista de diferencias f es una función de un solo argumento llamada append L , que, al recibir como argumento una lista enlazada X , devuelve una lista enlazada que contiene L antepuesta a X. La concatenación de listas de diferencias se implementa como una composición de funciones . El contenido se puede recuperar usando f[] . ^{[ 1 ]}

Esta implementación se utiliza habitualmente en lenguajes de programación funcional como Haskell , aunque también podría utilizarse en lenguajes imperativos.

Como funciones, las listas de diferencias son una representación de Cayley de listas como monoides, o más específicamente su monoide de transformación inducido por la multiplicación por la izquierda.

Ejemplos de uso se encuentran en el tipo ShowS en el Preludio de Haskell y en la biblioteca de listas de diferencias de Donald Bruce Stewart para Haskell . ^{[ 2 ]}

Otra implementación en el lenguaje de programación lógica Prolog utiliza variables de unificación. ^{[ 3 ]} Una lista de diferencias es un par OpenList-Hole , donde el primer elemento OpenList es una lista que contiene una variable de unificación no vinculada (hole) y el segundo elemento Hole es una referencia al agujero.