Programowanie funkcjonalne nie pozbywa się stanu. Wyjaśnia to tylko! Chociaż prawdą jest, że funkcje takie jak mapa często „rozplątują” „udostępnioną” strukturę danych, jeśli wszystko, co chcesz zrobić, to napisać algorytm osiągalności, wystarczy jedynie śledzić, które węzły już odwiedziłeś:
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]
Teraz muszę wyznać, że ręczne śledzenie tego stanu jest dość irytujące i podatne na błędy (łatwo użyć s zamiast s, łatwo przekazać te same s do więcej niż jednego obliczenia ...) . W tym momencie wkraczają monady: nie dodają niczego, czego wcześniej nie można było zrobić, ale pozwalają na niejawne przekazywanie zmiennej stanu, a interfejs gwarantuje, że dzieje się to w sposób jednowątkowy.
Edycja: Spróbuję podać bardziej uzasadnienie tego, co teraz zrobiłem: po pierwsze, zamiast po prostu testowania osiągalności, zakodowałem wyszukiwanie w pierwszej kolejności. Implementacja będzie wyglądać prawie tak samo, ale debugowanie wygląda trochę lepiej.
W języku stanowym DFS wyglądałby mniej więcej tak:
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)
Teraz musimy znaleźć sposób na pozbycie się stanu zmiennego. Przede wszystkim pozbywamy się zmiennej „visitlist”, powodując, że dfs zwraca, że zamiast 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))
A teraz przychodzi trudna część: pozbycie się zmiennej „odwiedzanej”. Podstawową sztuczką jest użycie konwencji, w której przekazujemy stan jako dodatkowy parametr do funkcji, które go potrzebują, i zwracają nową wersję stanu jako dodatkową wartość zwracaną, jeśli chcą ją zmodyfikować.
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...
Aby zastosować ten wzorzec do dfs, musimy go zmienić, aby otrzymać zestaw „odwiedzonych” jako dodatkowy parametr i zwrócić zaktualizowaną wersję „odwiedzonych” jako dodatkową wartość zwracaną. Dodatkowo musimy przepisać kod, abyśmy zawsze przekazywali „najnowszą” wersję „odwiedzanej” tablicy:
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)
Wersja Haskell robi prawie wszystko, co tutaj zrobiłem, z tym wyjątkiem, że działa całkowicie i wykorzystuje wewnętrzną funkcję rekurencyjną zamiast zmiennych zmiennych „curr_visited” i „childtrees”.
Jeśli chodzi o monady, to w zasadzie dokonują w sposób dorozumiany przekazywania „curr_visited”, zamiast zmuszania cię do zrobienia tego ręcznie. To nie tylko usuwa bałagan z kodu, ale także zapobiega popełnianiu błędów, takich jak rozwidlenie stanu (przekazanie tego samego „odwiedzonego” zestawu do dwóch kolejnych wywołań zamiast tworzenia łańcucha stanu).
