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 vinculada en el tiempo proporcional a su longitud. Las listas de diferencias se pueden implementar usando funciones de primera clase o usando unificación. El que una lista de diferencias sea más eficaz que otras representaciones de lista 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" efectivamente los cálculos de construcción de listas.
Implementación mediante funciones [ editar ]
Una lista diferencia f es un solo argumento función 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 composición de funciones . El contenido se puede recuperar usando f [] . [1]
Esta implementación se usa típicamente 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 multiplicación por la izquierda.
Los 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]
Implementación mediante unificación [ editar ]
Otra implementación en el lenguaje de programación lógica Prolog usa 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 ligada (agujero) y el segundo elemento Hole es una referencia al agujero.
Referencias [ editar ]
- ^ Una representación novedosa de listas y su aplicación a la función "inversa" por John Hughes (1986)
- ^ Listas de diferencias en Haskell (lenguaje de programación)
- ^ Listas abiertas y listas de diferencias en Prolog. Consultado el 17 de febrero de 2019.
 | Este artículo relacionado con algoritmos o estructuras de datos es un código auxiliar . Puedes ayudar a Wikipedia expandiéndolo . |
