La programmazione funzionale non elimina lo stato. Lo rende solo esplicito! Mentre è vero che funzioni come la mappa spesso "districano" una struttura dati "condivisa", se tutto ciò che vuoi è scrivere un algoritmo di raggiungibilità, allora è solo questione di tenere traccia di quali nodi hai già visitato:
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]
Ora, devo confessare che tenere traccia di tutto questo stato a mano è piuttosto fastidioso e soggetto a errori (è facile usare s 'invece di s' ', è facile passare lo stesso s' a più di un calcolo. ..). È qui che entrano le monadi: non aggiungono nulla che non potevi già fare prima, ma ti permettono di passare la variabile di stato attorno implicitamente e l'interfaccia garantisce che ciò avvenga in un modo a thread singolo.
Modifica: cercherò di dare un ulteriore ragionamento su ciò che ho fatto ora: prima di tutto, invece di testare solo la raggiungibilità, ho codificato una ricerca in profondità. L'implementazione sembrerà più o meno la stessa, ma il debug sembra un po 'meglio.
In un linguaggio di stato, il DFS sarebbe un po 'come questo:
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)
Ora dobbiamo trovare un modo per sbarazzarci dello stato mutabile. Prima di tutto ci liberiamo della variabile "visitlist" facendo sì che dfs restituisca quello invece di 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 ora arriva la parte difficile: sbarazzarsi della variabile "visitata". Il trucco di base è usare una convenzione in cui passiamo lo stato come parametro aggiuntivo alle funzioni che ne hanno bisogno e le funzioni restituiscono la nuova versione dello stato come valore di ritorno aggiuntivo se vogliono 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...
Per applicare questo modello al dfs, dobbiamo cambiarlo per ricevere il set "visitato" come parametro aggiuntivo e per restituire la versione aggiornata di "visitato" come un valore di ritorno extra. Inoltre, dobbiamo riscrivere il codice in modo da passare sempre in avanti la versione "più recente" dell'array "visited":
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 versione di Haskell fa più o meno quello che ho fatto qui, tranne che va fino in fondo e usa una funzione ricorsiva interna invece delle mutabili variabili "curr_visited" e "childtrees".
Per quanto riguarda le monadi, ciò che in pratica realizzano è far passare implicitamente il "curr_visited", invece di costringerti a farlo a mano. Non solo rimuove il disordine dal codice, ma impedisce anche di commettere errori, come lo stato di biforcazione (passando lo stesso set "visitato" a due chiamate successive anziché concatenare lo stato).
