Programowanie funkcjonalne i algorytmy stanowe

Uczę się programowania funkcjonalnego w Haskell . W międzyczasie studiuję teorię automatów, a ponieważ wydaje się, że obie pasują do siebie, piszę małą bibliotekę do zabawy z automatami.

Oto problem, który zmusił mnie do zadania pytania. Badając sposób oceny osiągalności stanu, wpadłem na pomysł, że prosty algorytm rekurencyjny byłby dość nieefektywny, ponieważ niektóre ścieżki mogą dzielić niektóre stany, a ja mógłbym je oceniać więcej niż raz.

Na przykład tutaj, oceny osiągalność o g z , to, że ma wykluczyć F zarówno podczas sprawdzania drogę przez D i C :

Mój pomysł jest taki, że algorytm działający równolegle na wielu ścieżkach i aktualizujący wspólny zapis stanów wykluczonych może być świetny, ale to dla mnie za dużo.

Widziałem, że w niektórych prostych przypadkach rekurencji można podać stan jako argument, i to właśnie muszę zrobić, ponieważ przekazuję listę stanów, przez które przeszedłem, aby uniknąć pętli. Ale czy istnieje sposób na przekazanie tej listy również do tyłu, na przykład zwrócenie jej w krotce wraz z logicznym wynikiem mojej canReachfunkcji? (choć wydaje się to trochę wymuszone)

Oprócz ważności mojego przykładowego przypadku , jakie inne techniki są dostępne w celu rozwiązania tego rodzaju problemów? Wydaje mi się, że muszą być na tyle powszechne, że muszą istnieć rozwiązania takie jak to, co dzieje się z fold*lub map.

Jak dotąd, czytając learnyouahaskell.com , nie znalazłem żadnego, ale uważam, że nie dotknąłem jeszcze monad.

(w razie zainteresowania opublikowałem kod w widoku kodu )

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

Oto prosta odpowiedź polegająca na 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

Gdzie neighborszwraca stany bezpośrednio związane ze stanem. Zwraca to szereg ścieżek.