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 O(1) eficiente y conversión a una lista enlazada en un tiempo proporcional a su longitud. Las listas de diferencias se pueden implementar utilizando funciones de primera clase o utilizando unificación. Si una lista de diferencias es más eficiente que 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" eficazmente los cálculos de construcción de listas.
Una lista de diferencias f es una función de un solo argumento append L , que cuando se le da una lista enlazada X como argumento , devuelve una lista enlazada que contiene L antepuesto a X . La concatenación de listas de diferencias se implementa como una función composition . El contenido se puede recuperar utilizando f [] . [1]
Esta implementación se utiliza normalmente en lenguajes de programación funcional como Haskell , aunque también podría usarse 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.
Algunos 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 hole.