Programación funcional y algoritmos de estado

12

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

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

Por ejemplo, aquí, al evaluar accesibilidad de g de a , tendría que excluir f ambos mientras comprueban la ruta a través de d y c :

Entonces,miideaesqueunalgoritmoquefuncioneenparaleloenmuchasrutasyqueactualiceunregistrocompartidodeestadosexcluidospodríaserexcelente,peroesoesdemasiadoparamí.

Hevistoqueenalgunoscasosderecursiónsimplessepuedepasarunestadocomoargumento,yesoesloquetengoquehaceraquí,porquepasolalistadeestadosquehepasadoparaevitarlosbucles.Pero,¿hayalgunaformadepasaresalistatambiénhaciaatrás,comodevolverlaenunatuplajuntoconelresultadobooleanodemifuncióncanReach?(aunqueestosesienteunpocoforzado)

Ademásdelavalidezdemicasodeejemplo,¿quéotrastécnicasestándisponiblespararesolverestetipodeproblemas?Creoqueestosdebenserlosuficientementecomunescomoparaquehayasolucionescomoloquesucedeconfold*omap.

Hastaahora,leyendo learnyouahaskell.com no encontré ninguno, pero considera que todavía no he tocado las mónadas.

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

    
pregunta bigstones 05.10.2013 - 00:29

2 respuestas

16

La programación funcional no se deshace del estado. ¡Sólo lo hace explícito! Si bien es cierto que las 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, solo es cuestión de mantener un registro 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' ([email protected](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 mantener un registro de todo este estado a mano es bastante molesto y propenso a errores (es fácil de 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 de manera implícita y la interfaz garantiza que suceda de una manera de un solo hilo.

Editar: Intentaré dar un razonamiento más amplio de lo que hice ahora: en primer lugar, en lugar de solo probar la accesibilidad, codifiqué una búsqueda en profundidad. 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 "lista de visitas" 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 pasemos el estado como un parámetro adicional a las funciones que lo necesiten y que esas funciones devuelvan la nueva versión del estado como un valor de retorno adicional si desean modificarla.

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, necesitamos 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, debemos volver a escribir el código para que siempre estemos pasando 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 prácticamente lo mismo que hice aquí, excepto que va hasta el final y usa una función recursiva interna en lugar de las 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 forking state (pasar el mismo conjunto "visitado" a dos llamadas posteriores en lugar de encadenar el estado).

    
respondido por el hugomg 05.10.2013 - 17:03
2

Aquí hay una respuesta simple basada en 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 neighbors devuelve los estados inmediatamente conectados a un estado. Esto devuelve una serie de rutas.

    
respondido por el jozefg 05.10.2013 - 04:17

Lea otras preguntas en las etiquetas