Programación funcional y algoritmos de estado.

Estoy aprendiendo programación funcional con Haskell . Mientras tanto, estoy estudiando la teoría de Autómatas y, como los dos parecen encajar bien, estoy escribiendo una pequeña biblioteca para jugar con autómatas.

Aquí está el problema que me hizo hacer la pregunta. Mientras estudiaba una forma de evaluar la accesibilidad de un estado, tuve la idea de que un algoritmo recursivo simple sería bastante ineficiente, porque algunas rutas podrían compartir algunos estados y podría terminar evaluándolos más de una vez.

Por ejemplo, aquí, al evaluar el alcance de g desde a , tendría que excluir f ambos al verificar la ruta a través de d y c :

Entonces, mi idea es que un algoritmo que funcione en paralelo en muchas rutas y actualice un registro compartido de estados excluidos podría ser excelente, pero eso es demasiado para mí.

He visto que en algunos casos simples de recursión uno puede pasar el estado como argumento, y eso es lo que tengo que hacer aquí, porque paso la lista de estados por los que he pasado para evitar bucles. Pero, ¿hay alguna manera de pasar esa lista también hacia atrás, como devolverla en una tupla junto con el resultado booleano de mi canReachfunción? (aunque esto se siente un poco forzado)

Además de la validez de mi caso de ejemplo , ¿qué otras técnicas están disponibles para resolver este tipo de problemas? Siento que estos deben ser lo suficientemente comunes como para que tenga que haber soluciones como lo que sucede con fold*o map.

Hasta ahora, leyendo learnyouahaskell.com no encontré ninguno, pero considero que todavía no he tocado mónadas.

( si está interesado, publiqué mi código en codereview )

La programación funcional no elimina el estado. ¡Solo lo hace explícito! Si bien es cierto que funciones como el mapa a menudo "desentrañarán" una estructura de datos "compartida", si todo lo que quiere hacer es escribir un algoritmo de accesibilidad, entonces solo es cuestión de hacer un seguimiento de los nodos que ya visitó:

import qualified Data.Set as S
data Node = Node Int [Node] deriving (Show)

-- Receives a root node, returns a list of the node keyss visited in a depth-first search
dfs :: Node -> [Int]
dfs x = fst (dfs' (x, S.empty))

-- This worker function keeps track of a set of already-visited nodes to ignore.
dfs' :: (Node, S.Set Int) -> ([Int], S.Set Int)
dfs' (node@(Node k ns), s )
  | k  `S.member` s = ([], s)
  | otherwise =
    let (childtrees, s') = loopChildren ns (S.insert k s) in
    (k:(concat childtrees), s')

--This function could probably be implemented as just a fold but Im lazy today...
loopChildren :: [Node] -> S.Set Int -> ([[Int]], S.Set Int)
loopChildren []  s = ([], s)
loopChildren (n:ns) s =
  let (xs, s') = dfs' (n, s) in
  let (xss, s'') = loopChildren ns s' in
  (xs:xss, s'')

na = Node 1 [nb, nc, nd]
nb = Node 2 [ne]
nc = Node 3 [ne, nf]
nd = Node 4 [nf]
ne = Node 5 [ng]
nf = Node 6 []
ng = Node 7 []

main = print $ dfs na -- [1,2,5,7,3,6,4]

Ahora, debo confesar que hacer un seguimiento manual de todo este estado es bastante molesto y propenso a errores (es fácil usar s 'en lugar de s' ', es fácil pasar la misma s' a más de un cálculo ...) . Aquí es donde entran las mónadas: no agregan nada que no pudieras hacer antes, pero te permiten pasar la variable de estado implícitamente y la interfaz garantiza que ocurra de una sola hebra.

Editar: Intentaré dar un razonamiento más de lo que hice ahora: en primer lugar, en lugar de solo probar la accesibilidad, codifiqué una búsqueda profunda. La implementación se verá más o menos igual, pero la depuración se ve un poco mejor.

En un lenguaje con estado, el DFS se vería así:

visited = set()  #mutable state
visitlist = []   #mutable state
def dfs(node):
   if isMember(node, visited):
       //do nothing
   else:
       visited[node.key] = true           
       visitlist.append(node.key)
       for child in node.children:
         dfs(child)

Ahora necesitamos encontrar una manera de deshacernos del estado mutable. En primer lugar, nos deshacemos de la variable "visitlist" haciendo que dfs devuelva eso en lugar de anular:

visited = set()  #mutable state
def dfs(node):
   if isMember(node, visited):
       return []
   else:
       visited[node.key] = true
       return [node.key] + concat(map(dfs, node.children))

Y ahora viene la parte difícil: deshacerse de la variable "visitada". El truco básico es utilizar una convención en la que pasamos el estado como un parámetro adicional a las funciones que lo necesitan y que esas funciones devuelvan la nueva versión del estado como un valor de retorno adicional si desean modificarlo.

let increment_state s = s+1 in
let extract_state s = (s, 0) in

let s0 = 0 in
let s1 = increment_state s0 in
let s2 = increment_state s1 in
let (x, s3) = extract_state s2 in
-- and so on...

Para aplicar este patrón a los dfs, debemos cambiarlo para recibir el conjunto "visitado" como un parámetro adicional y devolver la versión actualizada de "visitado" como un valor de retorno adicional. Además, necesitamos reescribir el código para que siempre pasemos la versión "más reciente" de la matriz "visitada":

def dfs(node, visited1):
   if isMember(node, visited1):
       return ([], visited1) #return the old state because we dont want to  change it
   else:
       curr_visited = insert(node.key, visited1) #immutable update, with a new variable for the new value
       childtrees = []
       for child in node.children:
          (ct, curr_visited) = dfs(child, curr_visited)
          child_trees.append(ct)
       return ([node.key] + concat(childTrees), curr_visited)

La versión de Haskell hace más o menos lo que hice aquí, excepto que va hasta el final y utiliza una función recursiva interna en lugar de variables mutables "curr_visited" y "childtrees".

En cuanto a las mónadas, lo que básicamente logran es pasar implícitamente el "curr_visited", en lugar de obligarlo a hacerlo a mano. Esto no solo elimina el desorden del código, sino que también evita que cometa errores, como bifurcar el estado (pasar el mismo conjunto "visitado" a dos llamadas posteriores en lugar de encadenar el estado).

Aquí hay una respuesta simple en la que confiar mapConcat.

 mapConcat :: (a -> [b]) -> [a] -> [b]
 -- mapConcat is in the std libs, mapConcat = concat . map
 type Path = []

 isReachable :: a -> Auto a -> a -> [Path a]
 isReachable to auto from | to == from = [[]]
 isReachable to auto from | otherwise = 
    map (from:) . mapConcat (isReachable to auto) $ neighbors auto from

Donde neighborsdevuelve los estados inmediatamente conectados a un estado. Esto devuelve una serie de caminos.