¿Qué hay de nuevo en estructuras de datos puramente funcionales desde Okasaki?

563

Desde el libro de 1998 de Chris Okasaki "Estructuras de datos puramente funcionales", no he visto aparecer muchas nuevas estructuras de datos puramente funcionales; Puedo nombrar solo algunos:

  • IntMap (también inventado por Okasaki en 1998, pero no presente en ese libro)
  • Árboles de dedos (y su generalización sobre monoides)

También hay algunas formas interesantes de implementar estructuras de datos ya conocidas, como el uso de "tipos anidados" o "tipos de datos algebraicos generalizados" para garantizar la invariabilidad de los árboles.

¿Qué otras ideas nuevas han aparecido desde 1998 en esta área?

jkff
fuente
20
Buena pregunta. Acabo de tener un estudiante preguntándome sobre esto, y no sabía la respuesta.
Suresh Venkat
Esto está bien por aquí, pero puede obtener mejores respuestas en Stack Overflow. Si pregunta allí, asegúrese de vincular la discusión aquí.
Charles Stewart
3
Bueno, el Haskell Reddit ha visto esto, por lo que también habrá algunas buenas respuestas, pero una excelente pregunta. Justo a la mitad del libro de Okasaki, me preguntaba lo mismo. +1
Robert Massaioli

Respuestas:

553

Nuevas estructuras de datos puramente funcionales publicadas desde 1998:

Conocido en 1997, pero no discutido en el libro de Okasaki:

  • Muchos otros estilos de árbol de búsqueda equilibrado . AVL, hermano, rango equilibrado, equilibrio acotado y muchos otros árboles de búsqueda equilibrados pueden (y han sido) implementados de manera puramente funcional mediante copia de ruta. Quizás merece una mención especial son:

    • Biased Search Trees , de Samuel W. Bent, Daniel D. Sleator y Robert E. Tarjan : un elemento clave en el artículo de Brodal et al. 2006 y el documento de Demaine et al. 2008.
  • Conjuntos infinitos que admiten una búsqueda rápida y exhaustiva , por Martín Escardó : Quizás no sea una estructura de datos per se .

  • Tres algoritmos en los árboles Braun , de Chris Okasaki : los árboles Braun ofrecen muchas operaciones de apilamiento en el peor de los casos O (lg n). Este límite es superado por muchas otras estructuras de datos, pero los árboles Braun tienen unaconsoperación perezosa en su segundo argumento, por lo que pueden usarse como pilas infinitas de alguna manera que otras estructuras no pueden.

  • El montón relajado min-max: una cola prioritaria fusionable de doble extremo y El montón KD: una cola prioritaria multidimensional eficiente , por Yuzheng Ding y Mark Allen Weiss : Estos son puramente funcionales, aunque esto no se discute en los documentos . No creo que los límites de tiempo alcanzados sean mejores que los que se pueden lograr usando árboles de dedos (de Hinze & Paterson o Kaplan & Tarjan) como colas de prioridad k-dimensionales, pero creo que las estructuras de Ding & Weiss usan menos espacio .

  • The Zipper , de Gérard Huet : Utilizado en muchas otras estructuras de datos (como los árboles de dedos de Hinze & Paterson), esta es una forma de convertir una estructura de datos al revés.

  • Las listas de diferencias son listas catenables O (1) con una transformación O (n) a conslistas habituales . Aparentemente se conocen desde la antigüedad en la comunidad Prolog, donde tienen una transformación O (1) a las conslistas habituales . La transformación O (1) parece ser imposible en la programación funcional tradicional, pero la abstracción de agujeros de Minamide , de POPL '98, discute una forma de permitir que O (1) agregue y la transformación O (1) dentro de la programación funcional pura. A diferencia de las implementaciones de programación funcional habituales de las listas de diferencias, que se basan en el cierre de funciones, las abstracciones de agujeros son esencialmente las mismas (tanto en su uso como en su implementación) que las listas de diferencias de Prolog. Sin embargo, parece que durante años la única persona que notó esto fueuno de los revisores de Minamide .

  • O(n)Θ(nlgn)Θ(nlgn)Θ(lg2n)

Principalmente estructuras de datos funcionales, antes, durante y después del libro de Okasaki:

  • O(m)mO(lglgn)

  • 1989: Árboles de búsqueda aleatoria por Cecilia R. Aragon y Raimund Seidel : Guy E. Blelloch y Margaret Reid-Miller analizaron estas cuestiones en un entorno puramente funcional en Operaciones de fraguado rápido con Treaps y Dan Blandford y Guy Blelloch en Operaciones de conjuntos funcionales con Treaps ( código) Proporcionan todas las operaciones de los dedos puramente funcionales y los árboles de búsqueda sesgados, pero requieren una fuente de aleatoriedad, lo que los hace no puramente funcionales. Esto también puede invalidar la complejidad temporal de las operaciones en treaps, suponiendo un adversario que puede cronometrar las operaciones y repetir las largas. (Esta es la misma razón por la cual los argumentos de amortización imperativa no son válidos en un entorno persistente, pero requiere un adversario con un cronómetro)

  • 1997: Skip-trees, una estructura de datos alternativa a Skip-lists en un enfoque concurrente , por Xavier Messeguer y Exploring the Duality Between Skip Lists and Binary Search Trees , por Brian C. Dean y Zachary H. Jones : las listas de omisión no son puramente funcional, pero pueden implementarse funcionalmente como árboles. Al igual que los treaps, requieren una fuente de bits aleatorios. (Es posible hacer que las listas de salto sean deterministas, pero, después de traducirlas a un árbol, creo que son solo otra forma de ver 2-3 árboles).

  • 1998: ¡ Todas las estructuras amortizadas en el libro de Okasaki! Okasaki inventó este nuevo método para mezclar la amortización y las estructuras de datos funcionales, que anteriormente se consideraban incompatibles. Depende de la memorización, que, como Kaplan y Tarjan han mencionado a veces, es en realidad un efecto secundario. En algunos casos ( como PFDS en SSD por razones de rendimiento ), esto puede ser inapropiado.

  • 1998: Listas de Catenable simples y persistentes con confianza , por Haim Kaplan, Chris Okasaki y Robert E. Tarjan : utiliza la modificación debajo del capó para proporcionar calcos catenables O (1) amortizados, presentando la misma interfaz que una anterior (puramente funcional, pero con memoria) ) versión que aparece en el libro de Okasaki. Kaplan y Tarjan habían creado anteriormente una estructura puramente funcional O (1) en el peor de los casos, pero es sustancialmente más complicada.

  • 2007: como se menciona en otra respuesta en esta página, estructuras de datos semipersistentes y persistente unión de hallazgos por Sylvain Conchon y Jean-Christophe Filliâtre

Técnicas para verificar estructuras de datos funcionales, antes, durante y después del libro de Okasaki:

Estructuras de datos imperativos o análisis no discutidos en el libro de Okasaki, pero relacionados con estructuras de datos puramente funcionales:

  • The Soft Heap: una cola de prioridad aproximada con una tasa de error óptima , por Bernard Chazelle : esta estructura de datos no usa matrices, por lo que ha tentado primero al canal #haskell IRC y luego a los usuarios de Stack Overflow , pero incluyedeleteen o (lg n) , que generalmente no es posible en un entorno funcional, y el análisis amortizado imperativo, que no es válido en un entorno puramente funcional.

  • Árboles de búsqueda binaria equilibrada con actualizaciones de dedo O (1) . En Making Data Structures Persistent , James R Driscoll, Neil Sarnak, Daniel D. Sleator y Robert E. Tarjan presentan un método para agrupar los nodos en un árbol rojo-negro para que las actualizaciones persistentes requieran solo espacio O (1). Los deques y árboles de dedos puramente funcionales diseñados por Tarjan, Kaplan y Mihaescu utilizan una técnica de agrupación muy similar para permitir actualizaciones de O (1) en ambos extremos. Los árboles AVL para la búsqueda localizada por Athanasios K. Tsakalidis funcionan de manera similar.

  • Montones de emparejamiento más rápidos o mejores límites para los montones de emparejamientos : desde que se publicó el libro de Okasaki, han aparecido varios análisis nuevos de montones de emparejamientos imperativos, incluidos los montones de emparejamientos con O (log log n) disminuyen el costo por Amr Elmasry y hacia un análisis final de los montones de emparejamientos por Seth Pettie. Es posible aplicar parte de este trabajo a los montones de emparejamiento perezoso de Okasaki.

  • Árboles dedos sesgados deterministas : En Listas Skip sesgada , por Amitabha Bagchi, Adam L. Buchsbaum, y Michael T. Goodrich, un diseño se presenta para las listas de salto sesgadas deterministas. A través de la lista de salto / transformación de árbol mencionada anteriormente, puede ser posible hacer árboles de búsqueda sesgados deterministas. Las listas de salto sesgadas con los dedos descritas por John Iacono y Özgür Özkan en Mergeable Dictionaries podrían ser posibles en los árboles de salto sesgados. Demaine et al. Sugieren un árbol de dedos sesgado. en su artículo sobre intentos puramente funcionales (ver arriba) como una forma de reducir los límites de tiempo y espacio en la actualización de los dedos en los intentos.

  • The String B-Tree: una nueva estructura de datos para la búsqueda de cadenas en la memoria externa y sus aplicaciones por Paolo Ferragina y Roberto Grossi es una estructura de datos bien estudiada que combina los beneficios de los intentos y los B-trees.

jbapple
fuente
55
No recuerdo haber marcado la casilla "wiki de la comunidad" en esta respuesta. ¿Hay alguna forma de deshacer eso?
jbapple
77
@jbapple: después de un cierto número de ediciones, todas las publicaciones se convierten en wiki de la comunidad. Esa es una revisión impresionantemente exhaustiva allí. Gracias.
Phil Miller el
29
Gran lista! Lo que me hace desear que Okasaki publique una segunda edición.
Radu GRIGore
44
Tenga en cuenta que Isabelle / HOL puede generar código para SML, OCaml, Haskell, Scala. La herramienta Haskabelle también puede importar Haskell a Isabelle / HOL.
Makarius
2
La terminología de "extracción de programa" es una de Coq: toma una prueba constructiva y crea un programa ejecutable a partir de ella, eliminando algunas cosas. En Isabelle, esto se llama "generación de código" y funciona de manera diferente, utilizando las especificaciones HOL como pseudocódigo, no como pruebas. La extracción de pruebas en Isabelle / HOL según Berghofer funciona como Coq, pero rara vez se usa en estos días.
Makarius
63

A las excelentes notas ya hechas, agregaré Zippers .

Huet, Gerard. "Functional Pearl: The Zipper" Journal of Functional Programming 7 (5): 549-554, septiembre de 1997.

Wikipedia: Cremallera (estructura de datos)

Matt podría
fuente
44
Las cremalleras son IMPRESIONANTES. Para muchos casos de uso, que permiten representaciones basadas en árboles para convertirse en la opción "correcta" para muchos tipos de datos que de otro modo sería un poco más complicado
Carter Tazio Schonwald
1
Un ejemplo de su uso para la manipulación de XML: anti-xml.org/zippers.html
Caracol mecánico
40

Conchon, Filliatre, una estructura de datos persistente UNION-FIND y estructuras de datos semipersistentes .

Radu GRIGore
fuente
¡Guau, una persistente UNION-FIND! ¡Gracias!
jkff
3
Bueno, algo así como ... Ver el artículo.
Radu GRIGore
1
... o, si lo prefiere, vea un código (por Matt Parkinson) github.com/septract/jstar/blob/master/src/utils/…
Radu GRIGore
55
Ahora veo por qué el comentario "tipo de ..." tuvo un voto positivo. Tienen un buen rendimiento solo cuando uno casi exclusivamente no usa persistencia o retrocede todo el tiempo: si a menudo usa versiones "nuevas" y "viejas", está jodido. Buena idea de rerooting.
jkff
El enlace de Radu ahora se puede encontrar en github.com/septract/jstar-old/blob/…
jbapple
20

Agregaría la versión de cremalleras de McBride como derivados de tipos de datos.

ninguna
fuente
Amo esas cosas ¡Es tan genial que el derivado tenga una aplicación tan diferente de encontrar tasas de cambio!
SamB
3
SamB, también te pueden interesar las derivadas de expresiones regulares (si aún no las conocías).
jbapple
14

Rangemaps

Es una estructura de datos especializada, pero se puede usar como un sustituto de la DIETA de Martin Erwig, con propiedades ligeramente diferentes, por lo que al menos hay una estructura de datos existente para compararla. La DIETA misma se describió en un artículo en JFP en 1998, por lo que quizás no se incluye en las Estructuras de datos puramente funcionales.

Complicado ver bio
fuente
7

En seguimiento al documento de 2012 vinculado anteriormente, el trabajo sobre los vectores RRB se ha extendido y publicado en ICFP'15.

Vector RRB: una secuencia inmutable práctica de propósito general http://dl.acm.org/citation.cfm?id=2784739

Mike Rainey
fuente