functional-programming - mitocode - programacion funcional c#

¿Cómo implemento gráficos y algoritmos de gráficos en un lenguaje de programación funcional?

Question

Básicamente, sé cómo crear estructuras de datos de gráficos y usar el algoritmo de Dijkstra en lenguajes de programación donde se permiten los efectos secundarios. Normalmente, los algoritmos de gráficos usan una estructura para marcar ciertos nodos como ''visitados'', pero esto tiene efectos secundarios, que trato de evitar.

Puedo pensar en una forma de implementar esto en un lenguaje funcional, pero básicamente requiere pasar grandes cantidades de estado a diferentes funciones, y me pregunto si hay una solución más eficiente en términos de espacio.

Answer 1

Aquí hay un ejemplo de Swift. Puede encontrar esto un poco más legible. Las variables tienen un nombre descriptivo, a diferencia de los ejemplos súper crípticos de Haskell.

https://github.com/gistya/Functional-Swift-Graph

Answer 2

La mayoría de los lenguajes funcionales admiten funciones internas. De modo que puede crear su representación gráfica en la capa más externa y simplemente hacer referencia a ella desde la función interna.

Este libro lo cubre ampliamente http://www.amazon.com/gp/product/0262510871/ref=pd_lpo_k2_dp_sr_1?ie=UTF8&cloe_id=aa7c71b1-f0f7-4fca-8003-525e801b8d46&attrMsgId=LPWidget-A1&pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0262011530&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=114DJE8K5BG75B86E1QS

Answer 3

Me encantaría escuchar acerca de alguna técnica realmente inteligente, pero creo que hay dos enfoques fundamentales:

1. Modificar algún objeto de estado global. es decir, efectos secundarios
2. Pase el gráfico como un argumento para sus funciones con el valor de retorno como el gráfico modificado. Supongo que este es su enfoque de "pasar grandes cantidades de estado"

Eso es lo que se hace en la programación funcional. Si el compilador / intérprete es bueno, te ayudará a administrar la memoria. En particular, querrás asegurarte de utilizar recursividad final, si recurres en cualquiera de tus funciones.

Answer 4

Puede ver cómo funciona la biblioteca de gráficos funcionales Haskell de Martin Erwig. Por ejemplo, sus funciones de ruta más corta son todas puras, y puede ver el código fuente de cómo se implementa.

Otra opción, como fmark mencionado , es usar una abstracción que le permita implementar funciones puras en términos de estado. Él menciona la mónada estatal (que está disponible tanto en variedades lazy como strict ). Otra opción, si estás trabajando en el compilador / intérprete GHC Haskell (o, en mi opinión, cualquier implementación Haskell que soporte tipos de rango 2), otra opción es la mónada ST , que te permite escribir funciones puras que se relacionan con mutable variables internamente

Answer 5

Si estuviera usando haskell, el único lenguaje funcional con el que estoy familiarizado, recomendaría usar la mónada de estado . La mónada de estado es una abstracción para una función que toma un estado y devuelve un valor intermedio y un nuevo valor de estado. Esto se considera haskell idiomático para aquellas situaciones donde es necesario mantener un estado grande.

Es una alternativa mucho más agradable a la ingenua expresión de "devolver el estado como resultado de una función y pasarla como un parámetro" que se enfatiza en los tutoriales de programación funcional para principiantes. Imagino que la mayoría de los lenguajes de programación funcionales tienen una construcción similar.

Answer 6

Solo guardo el conjunto visitado como un conjunto y lo paso como un parámetro. Existen implementaciones eficientes de tiempo de registro de conjuntos de cualquier tipo ordenado y conjuntos de enteros extraeficientes.

Para representar un gráfico, uso listas de adyacencia, o utilizaré un mapa finito que correlaciona cada nodo con una lista de sus sucesores. Depende de lo que quiero hacer.

En lugar de Abelson y Sussman, recomiendo Purely Functional Data Structures de Chris Okasaki. Me he relacionado con la disertación de Chris, pero si tienes el dinero, lo expandió en un excelente libro .

Solo por sonrisas, aquí hay una búsqueda de profundidad de postorder invertida ligeramente aterradora realizada en estilo de continuación y paso en Haskell. Esto es directamente de la biblioteca del optimizador de Hoopl :

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e)
                          => LabelMap (block C C) -> e -> LabelSet -> [block C C]
postorder_dfs_from_except blocks b visited =
 vchildren (get_children b) (/acc _visited -> acc) [] visited
 where
   vnode :: block C C -> ([block C C] -> LabelSet -> a) 
                      -> ([block C C] -> LabelSet -> a)
   vnode block cont acc visited =
        if setMember id visited then
            cont acc visited
        else
            let cont'' acc visited = cont (block:acc) visited in
            vchildren (get_children block) cont'' acc (setInsert id     visited)
      where id = entryLabel block
   vchildren bs cont acc visited = next bs acc visited
      where next children acc visited =
                case children of []     -> cont acc visited
                                 (b:bs) -> vnode b (next bs) acc     visited
   get_children block = foldr add_id [] $ targetLabels bloc
   add_id id rst = case lookupFact id blocks of
                      Just b -> b : rst
                      Nothing -> rst