Actualmente estoy jugando con LISP (particularmente Scheme y Clojure) y me pregunto cómo se tratan las estructuras de datos típicas en lenguajes de programación funcionales.
Por ejemplo, digamos que me gustaría resolver un problema usando un algoritmo de trazado de ruta de gráfico. ¿Cómo se podría representar ese gráfico en un lenguaje de programación funcional (principalmente interesado en el estilo funcional puro que se puede aplicar a LISP)? ¿Me olvidaría de los gráficos por completo y resolvería el problema de otra manera?
Los lenguajes funcionales manejan las estructuras de datos de la misma manera que los lenguajes no funcionales: separando la interfaz de la implementación, creando tipos de datos abstractos.
Puede crear tipos de datos abstractos en Lisp. Por ejemplo, para un gráfico, es posible que desee un par de funciones:
Una vez que haya creado esa interfaz en un gráfico, puede implementar las estructuras de datos reales de muchas maneras diferentes, posiblemente optimizando factores tales como la eficiencia del programador, la flexibilidad y la eficiencia computacional.
La clave es asegurarse de que el código que usa gráficos solo use la interfaz de gráficos y no acceda a la implementación subyacente. Esto mantendrá el código del cliente más simple ya que está desacoplado de la implementación real.
fuente
Bueno, dependería de si su gráfico es dirigido / no dirigido, ponderado / no ponderado, pero una forma de representar un gráfico ponderado dirigido (que sería el más general) es con un mapa de mapas (en Clojure)
representaría un mapa con nodos: a: byc: : a apunta a: b con un peso de 3 y: c con un peso de 4.: b apunta a: a con un peso de 1.: c no apunta a nada.
fuente
En Common Lisp, si necesito representar un árbol, usaría una lista (si fuera solo para un truco rápido) o definiría una clase de árbol (o estructura, pero las clases interactúan bien con funciones genéricas, entonces ¿por qué no?) .
Si necesito árboles literales en el código, probablemente también defina una
make-tree
función que tome una representación de la lista del árbol que quiero y la convierta en un árbol de objetos de árbol.fuente
En Haskell, la lista es la estructura de datos básica y, si desea estructuras de datos más avanzadas, a menudo utiliza estructuras recursivas como si un árbol es nulo o un nodo y dos árboles
fuente