Programmation fonctionnelle et algorithmes avec état

J'apprends la programmation fonctionnelle avec Haskell . En attendant, j'étudie la théorie des automates et comme les deux semblent bien s'accorder, j'écris une petite bibliothèque pour jouer avec les automates.

Voici le problème qui m'a fait poser la question. En étudiant un moyen d'évaluer l'accessibilité d'un état, j'ai eu l'idée qu'un simple algorithme récursif serait assez inefficace, car certains chemins pourraient partager certains états et je pourrais finir par les évaluer plus d'une fois.

Par exemple, ici, pour évaluer l' accessibilité de g à partir de a , je devrais exclure f à la fois tout en vérifiant le chemin passant par d et c :

Mon idée est donc qu'un algorithme fonctionnant en parallèle sur de nombreux chemins et mettant à jour un enregistrement partagé d'états exclus pourrait être formidable, mais c'est trop pour moi.

J'ai vu que dans certains cas de récursivité simples, on peut passer l'état comme argument, et c'est ce que je dois faire ici, car je transmets la liste des états que j'ai traversés pour éviter les boucles. Mais existe-t-il un moyen de passer cette liste également en arrière, comme la renvoyer dans un tuple avec le résultat booléen de ma canReachfonction? (même si cela semble un peu forcé)

Outre la validité de mon exemple , quelles autres techniques sont disponibles pour résoudre ce type de problèmes? Je pense que celles-ci doivent être suffisamment courantes pour qu'il y ait des solutions comme ce qui se passe avec fold*ou map.

Jusqu'à présent, en lisant Learnyouahaskell.com, je n'en ai pas trouvé, mais considérez que je n'ai pas encore touché aux monades.

( si intéressé, j'ai posté mon code sur codereview )

La programmation fonctionnelle ne se débarrasse pas de l'état. Cela ne fait que le rendre explicite! Bien qu'il soit vrai que des fonctions comme map "démêlent" souvent une structure de données "partagée", si tout ce que vous voulez faire est d'écrire un algorithme d'accessibilité, il suffit de garder une trace des nœuds que vous avez déjà visités:

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]

Maintenant, je dois avouer que garder une trace de tout cet état à la main est assez ennuyeux et sujet aux erreurs (il est facile d'utiliser s au lieu de s '', il est facile de passer le même s 'à plus d'un calcul ...) . C'est là que les monades entrent en jeu: elles n'ajoutent rien que vous ne pouviez pas déjà faire auparavant, mais elles vous permettent de passer la variable d'état implicitement et l'interface garantit que cela se produit de manière monothread.

Edit: je vais essayer de donner un raisonnement plus approfondi de ce que j'ai fait maintenant: tout d'abord, au lieu de simplement tester l'accessibilité, j'ai codé une recherche en profondeur d'abord. L'implémentation va ressembler à peu près mais le débogage est un peu meilleur.

Dans un langage avec état, le DFS ressemblerait un peu à ceci:

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)

Maintenant, nous devons trouver un moyen de se débarrasser de l'état mutable. Tout d'abord, nous nous débarrassons de la variable "visitlist" en faisant revenir dfs au lieu 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))

Et maintenant vient la partie délicate: se débarrasser de la variable "visitée". L'astuce de base consiste à utiliser une convention dans laquelle nous passons l'état en tant que paramètre supplémentaire aux fonctions qui en ont besoin et demandons à ces fonctions de renvoyer la nouvelle version de l'état en tant que valeur de retour supplémentaire si elles souhaitent le modifier.

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

Pour appliquer ce modèle au DFS, nous devons le changer pour recevoir le jeu "visité" comme paramètre supplémentaire et pour renvoyer la version mise à jour de "visité" comme valeur de retour supplémentaire. De plus, nous devons réécrire le code afin de toujours transmettre la version "la plus récente" du tableau "visité":

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 version Haskell fait à peu près ce que j'ai fait ici, sauf qu'elle va jusqu'au bout et utilise une fonction récursive interne au lieu des variables "curr_visited" et "childtrees" mutables.

Quant aux monades, ce qu'elles accomplissent essentiellement est de passer implicitement le "curr_visited", au lieu de vous forcer à le faire à la main. Non seulement cela supprime l'encombrement du code, mais il vous empêche également de faire des erreurs, telles que l'état de forking (passer le même ensemble "visité" à deux appels suivants au lieu de chaîner l'état).

Voici une réponse simple sur laquelle s'appuyer 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

Où neighborsrenvoie les états immédiatement connectés à un état. Cela renvoie une série de chemins.