Programação funcional e algoritmos com estado

Estou aprendendo programação funcional com Haskell . Enquanto isso, estou estudando a teoria dos autômatos e, como os dois parecem se encaixar bem, estou escrevendo uma pequena biblioteca para brincar com autômatos.

Aqui está o problema que me fez fazer a pergunta. Enquanto estudava uma maneira de avaliar a acessibilidade de um estado, tive a idéia de que um algoritmo recursivo simples seria bastante ineficiente, porque alguns caminhos podem compartilhar alguns estados e eu posso acabar avaliando-os mais de uma vez.

Por exemplo, aqui, avaliar a acessibilidade de g de um , eu teria que excluir f tanto ao verificar o caminho através d e c :

Então, minha ideia é que um algoritmo trabalhando em paralelo em muitos caminhos e atualizando um registro compartilhado de estados excluídos possa ser ótimo, mas isso é demais para mim.

Vi que, em alguns casos simples de recursão, é possível passar estado como argumento, e é isso que tenho que fazer aqui, porque passo adiante a lista de estados pelos quais passei para evitar loops. Mas existe uma maneira de passar essa lista também para trás, como devolvê-la em uma tupla junto com o resultado booleano da minha canReachfunção? (embora isso pareça um pouco forçado)

Além da validade do meu caso de exemplo , que outras técnicas estão disponíveis para resolver esse tipo de problema? Eu sinto que estes devem ser comuns o suficiente para que haja soluções como o que acontece com fold*ou map.

Até agora, lendo learnyouahaskell.com eu não encontrei nenhum, mas considere que ainda não toquei em mônadas.

( se estiver interessado, publiquei meu código na visualização de código )

A programação funcional não se livra do estado. Isso apenas torna explícito! Embora seja verdade que funções como map frequentemente "desvendam" uma estrutura de dados "compartilhada", se tudo o que você quer fazer é escrever um algoritmo de alcançabilidade, é apenas uma questão de acompanhar quais nós você já visitou:

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]

Agora, devo confessar que acompanhar todo esse estado manualmente é bastante irritante e propenso a erros (é fácil usar s 'em vez de s' ', é fácil passar os mesmos s' para mais de uma computação ...) . É aqui que as mônadas entram: elas não adicionam nada que você já não podia fazer antes, mas permitem passar a variável de estado implicitamente e a interface garante que isso aconteça de maneira única.

Edit: tentarei explicar melhor o que fiz agora: primeiro, em vez de apenas testar a acessibilidade, codifiquei uma pesquisa profunda. A implementação terá a mesma aparência, mas a depuração parecerá um pouco melhor.

Em uma linguagem stateful, o DFS ficaria assim:

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)

Agora precisamos encontrar uma maneira de nos livrarmos do estado mutável. Antes de tudo, nos livramos da variável "visitlist" fazendo com que o dfs retorne isso em vez de void:

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))

E agora vem a parte complicada: livrar-se da variável "visitada". O truque básico é usar uma convenção na qual passamos o estado como um parâmetro adicional para funções que precisam dele e essas funções retornam a nova versão do estado como um valor de retorno extra, se quiserem modificá-lo.

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 esse padrão aos dfs, precisamos alterá-lo para receber o conjunto "visitado" como um parâmetro extra e retornar a versão atualizada de "visitado" como um valor de retorno extra. Além disso, precisamos reescrever o código para sempre transmitir a versão "mais recente" da 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)

A versão Haskell faz praticamente o que eu fiz aqui, exceto que ela percorre todo o caminho e usa uma função recursiva interna em vez de variáveis ​​mutáveis ​​"curr_visited" e "childtrees".

Quanto às mônadas, o que elas basicamente realizam é ​​passar implicitamente o "curr_visited", em vez de forçar você a fazer isso manualmente. Isso não apenas remove a desordem do código, mas também evita que você cometa erros, como o estado de bifurcação (passando o mesmo conjunto "visitado" para duas chamadas subseqüentes em vez de encadear o estado).

Aqui está uma resposta simples, com base 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

Onde neighborsretorna os estados imediatamente conectados a um estado. Isso retorna uma série de caminhos.