data structures - programacion - ¿Algunas estructuras de datos son más adecuadas para la programación funcional que otras?

programacion funcional preguntas (9)

¿Existen patrones de uso realmente diferentes para las estructuras de datos entre la programación funcional y la imperativa?

Grandes, gigantescos, de día y de noche, en gran parte porque los efectos secundarios no son tolerados en la programación funcional.

Si es así, ¿es esto un problema?

El problema radica en los paradigmas imperativos que no podrán mantener la eficiencia a medida que la paralelización sea más necesaria; la única salida para estos idiomas será deshacerse de los efectos secundarios, pero luego se convertirán en lenguajes funcionales rotos, pero entonces, ¿por qué debería hacerlo? Me molesto con ellos cuando hay algunos lenguajes funcionales que funcionan bastante bien. Además, la semántica de los lenguajes funcionales es más fácil de controlar, por lo tanto, los programas funcionales pueden demostrarse correctos, mientras que sus homólogos de C ++ no pueden (aún así, de todos modos). Por lo tanto, muchas herramientas de verificación formales se basan en lenguajes funcionales; por ejemplo, ACL2 se basa en la concordancia común y Cryptol se basa en Haskell. Dado que la verificación formal es la ola del futuro, los lenguajes funcionales se pueden integrar mejor con esas herramientas. En resumen, diga adiós a C, C ++ y demás: ¡buena confianza! Alguien debería haber tomado un 30 debería 6 hace mucho tiempo.

¿Qué pasa si realmente necesitas una tabla hash para alguna aplicación? ¿Simplemente se traga el gasto extra incurrido por modificaciones?

La ola del futuro es la siguiente: usted escribe una programación funcional especificando una tabla hash, el lenguaje que usa es cryptol. Cuando haya terminado y haya probado que su programa funciona, presiona un botón y aparece una versión eficiente que usa una tabla hash si se ha decidido que es lo mejor que se debe usar.

En Real World Haskell , hay una sección titulada "Vida sin arrays o tablas hash" en la que los autores sugieren que la lista y los árboles son los preferidos en la programación funcional, mientras que una matriz o una tabla hash podrían usarse en un programa imperativo.

Esto tiene sentido, ya que es mucho más fácil reutilizar parte de una lista o árbol (inmutable) cuando se crea uno nuevo que hacerlo con una matriz.

Así que mis preguntas son:

¿Existen patrones de uso realmente diferentes para las estructuras de datos entre la programación funcional y la imperativa?
Si es así, ¿es esto un problema?
¿Qué pasa si realmente necesitas una tabla hash para alguna aplicación? ¿Simplemente se traga el gasto extra incurrido por modificaciones?

El libro Estructuras de datos puramente funcionales cubre sus preguntas en profundidad e incluye una gran combinación de teorías e implementaciones principalmente en ML: el apéndice también contiene implementaciones de Haskell, por lo que debería poder seguir un poco de página extra. Es una lectura bastante buena (aunque difícil en algunas partes) si está realmente interesado en una respuesta completa a sus preguntas. Habiendo dicho eso, creo que efímero dio una excelente respuesta corta.

edición: Steven Huwig proporcionó un link a la tesis de que el libro comenzó como. Si bien no lo he leído, lo único que falta (a juzgar por la tabla de contenido) son las implementaciones de Haskell.

En lo que respecta a las tablas hash en lenguajes funcionales: como ACL2 se mencionó anteriormente, señalaré que hay una biblioteca de "hash cons" para ACL2 que proporciona la historia lógica que es básicamente una asociación de listas semánticas pero que tiene el rendimiento de una tabla hash. (Por ejemplo, puede buscar un valor en una tabla usando hons-get). Si está interesado, consulte el tema "hons" en los manuales de usuarios de ACL2.

Hablando como alguien que ha estado haciendo OO durante muchos años, y recientemente ha estado construyendo un proyecto grande que requiere una gran cantidad de velocidad (un sistema de comercio de opciones automatizado en tiempo real) en Haskell:

¿Existen patrones de uso realmente diferentes para las estructuras de datos entre la programación funcional y la imperativa?

Si estás hablando de Haskell, sí, mucho. Sin embargo, gran parte de esto se debe a la pureza; las diferencias son algo menores en otros lenguajes funcionales donde los datos mutables se utilizan más a menudo. Dicho esto, como han señalado otros, el código y las estructuras recursivas se usan mucho más en todos o casi todos los lenguajes funcionales.

Si es así, ¿es esto un problema?

No ha sido para mí, aparte de tener que dedicar un tiempo para aprender la nueva forma de trabajar. En particular, el rendimiento ciertamente no ha sido un problema: el sistema en el que estoy trabajando se ejecuta considerablemente más rápido que la implementación Java anterior, por ejemplo.

¿Qué pasa si realmente necesitas una tabla hash para alguna aplicación? ¿Simplemente se traga el gasto extra incurrido por modificaciones?

En general, el problema no es que "realmente necesita una tabla hash", sino que necesita acceso a ciertos datos dentro de ciertas restricciones de tiempo (lo que puede ser "lo más rápido posible en un hardware determinado"). Para eso, miras a tu alrededor y haces lo que necesitas hacer. Si eso incluye introducir la mutabilidad, no veo un gran problema con eso, y puedes hacerlo en Haskell, aunque puede que no sea tan conveniente como en otros idiomas. Pero tenga en cuenta que si tiene un problema de esta naturaleza, ciertamente no va a ser tan simple como, "use una tabla hash genérica y listo". El rendimiento extremadamente alto para una funcionalidad particular en una plataforma de hardware particular invariablemente requiere mucho trabajo, y generalmente más que algunos trucos. En mi opinión, preferir una implementación de idioma sobre otra simplemente porque tiene algo que funciona mejor que en otros idiomas es, en mi opinión, un enfoque poco sofisticado para la ingeniería de software que no es probable que produzca resultados consistentes.

La tesis de Chris Okasaki, link , está disponible de forma gratuita en línea. Cubre muchas estrategias diferentes para la representación de datos persistentes e inmutables.

Si realmente necesita una tabla hash, considere que una búsqueda O (lg n) es solo veinte veces más lenta que una búsqueda O (1) cuando está buscando un millón de elementos.

Los programas funcionales tienden a poner más énfasis en la recursión. Esto, a su vez, sugiere el uso de algoritmos recursivos y estructuras de datos recursivos. Tanto las listas como los árboles son estructuras recursivas (el enlace "siguiente" en una lista es otra lista, y los hijos de un nodo de árbol son ambos árboles).

Es posible que desee reconsiderar si está considerando un gasto adicional en un algoritmo. ¿Por qué la tabla hash (que es O (1) para un algoritmo no recursivo) incurre en un gasto adicional? ¿Qué ventaja está obteniendo al usarlo, en lugar de un árbol o lista?

Sí, la principal diferencia es la inmutabilidad de los datos, que puede incluir código (ver funciones de orden superior). Consulte la página de Wikipedia en Purely Functional para obtener una lista de los tipos de datos y usos comunes. Si es un problema o no, depende de cómo lo mires. La programación en un lenguaje funcional tiene muchas ventajas si se ajusta al tipo de tarea en la que está trabajando. Una tabla hash es un tipo de matriz asociativa, pero no es la que se quiere usar en un lenguaje funcional debido a la repetición que tendría que hacer en la inserción y al bajo rendimiento sin matrices. En su lugar, intente la implementación de Haskell de Data.Map para una matriz asociativa.

Sí, los patrones de uso son dramáticamente diferentes, pero no, no es un problema. Si desea una tabla hash, generalmente quiere decir que desea un mapa finito con claves de cadena y acceso rápido. Los árboles de búsqueda ternarios de Bentley y Sedgewick son puramente funcionales y, al menos en algunos casos, superan a las tablas hash.

Como se mencionó anteriormente, el libro de Chris Okasaki sobre estructuras de datos puramente funcionales es muy bueno.

Sí. Normalmente, las tuplas, las listas y las funciones evaluadas parcialmente son estructuras de datos muy comunes en los lenguajes de programación funcionales. Las estructuras de datos mutables, como los arreglos y las tablas hash (reales), se usan mucho menos porque no encajan tan bien con Haskell. SML (que también es funcional, pero no perezoso) puede usar arreglos de forma más natural que Haskell, pero las listas son aún más comunes porque se mapean bien a algoritmos recursivos.
No estoy seguro de cómo responder a esto. Un problema para quien?
Existen implementaciones de matrices asociativas ("tabla hash" equivalente) que pueden continuar compartiendo la mayor parte de su estructura subyacente incluso después de diferentes actualizaciones. Creo que el Data.Map de GHC lo hace; Además, Edison tiene bastantes estructuras de datos perezosas / funcionales.