Hace algunos meses leí en algún lugar un enfoque eficiente para agregar y anteponer listas a otras listas en O (1) representándolas con composiciones de funciones que, una vez evaluadas, compilan O (n) la lista resultante.lista eficiente anexar/anteponer a través de la composición de función
Desafortunadamente no recuerdo el origen de este artículo o (si existe) el nombre de esta técnica/enfoque. ¿Tiene referencias al respecto, por favor?
La estructura de datos se denomina lista de diferencias (o DList para abreviar). Puede encontrar una implementación predeterminada de él in a library available on Hackage.
Como mencionaste, se puede obtener una descripción completa en a chapter in Real World Haskell on the subject.
¡Genial, gracias! Eso es exactamente lo que estaba buscando. Buscando un poco Google 'DList', descubrí que en realidad estaba buscando el capítulo 13 de" Real World Haskell "de Don Stewart ... aquí está la explicación completa de cómo funcionan esas listas: http: // book. realworldhaskell.org/read/data-structures.html#data.dlist ¿Podría poner un enlace al libro en la respuesta como referencia futura, por favor? Gracias –
También se menciona en LYAH: http://learnyouahaskell.com/for-a-few-monads-more, capítulo "Listas de diferencias" – efie
@Riccardo La lista original de diferencias nació en Prolog, y no consiste en nada más que una lista de enlace único que también lleva alrededor del puntero a su última celda de cons, de modo que se puede extender de manera eficiente. En Prolog sin retroceso, como en Haskell, una vez que se establece un puntero, no se puede cambiar. Se implementa fácilmente en C y se puede hacer que parezca inmutable añadiendo otro campo de datos, * longitud *, a la estructura de datos, por lo que no se permite el acceso más allá de ese punto. Extenderlo haría una copia con una nueva longitud pero la misma lista subyacente. (implementadores, ¡NB!) :) –
Debe estar pensando en ShowS y amigos del Preludio. Ver here.
La primera aparición (probable) fue en un documento de John Hughes "Una nueva representación de listas y su aplicación a la función 'Reverse'" (creo que eran folclore antes de esto) - por lo tanto, también se las denomina _Hughes Lists_. Tenga en cuenta que solo admiten la ** construcción ** eficiente: el paquete DList en Hackage tiene una API que admite _introspección_, pero para implementar la introspección debe metamorfosearse en una lista normal y volver a salir. Esto es ineficiente: si quieres introspección, quieres una estructura diferente. –
Es una compensación bastante justa cuando no se necesita introspección. Gracias por señalarlo. No estoy buscando una estructura de datos para usar en este momento, sin embargo, solo quería estudiar la implementación para las listas de diferencias/Hughes. –