Funktionale Programmierung und zustandsbehaftete Algorithmen

Ich lerne funktionale Programmierung mit Haskell . In der Zwischenzeit studiere ich Automatentheorie und da die beiden gut zusammenpassen, schreibe ich eine kleine Bibliothek, um mit Automaten zu spielen.

Hier ist das Problem, bei dem ich die Frage gestellt habe. Während ich einen Weg studierte, die Erreichbarkeit eines Zustands zu bewerten, kam ich auf die Idee, dass ein einfacher rekursiver Algorithmus ziemlich ineffizient wäre, da einige Pfade einige Zustände gemeinsam haben und ich sie möglicherweise mehrmals auswerten würde.

Wenn Sie hier beispielsweise die Erreichbarkeit von g von a aus bewerten , müssen Sie f beide ausschließen, während Sie den Pfad durch d und c überprüfen :

Meine Idee ist also, dass ein Algorithmus, der auf vielen Pfaden parallel arbeitet und einen gemeinsamen Datensatz ausgeschlossener Zustände aktualisiert, großartig sein könnte, aber das ist zu viel für mich.

Ich habe gesehen, dass in einigen einfachen Rekursionsfällen ein Zustand als Argument übergeben werden kann, und das muss ich hier tun, weil ich die Liste der Zustände weitergebe, die ich durchlaufen habe, um Schleifen zu vermeiden. Aber gibt es eine Möglichkeit, diese Liste auch rückwärts zu übergeben, wie sie zusammen mit dem booleschen Ergebnis meiner canReachFunktion in einem Tupel zurückzugeben ? (obwohl sich das ein bisschen gezwungen anfühlt)

Welche anderen Techniken stehen neben der Gültigkeit meines Beispielfalls zur Lösung dieser Art von Problemen zur Verfügung? Ich bin der Meinung, dass dies so verbreitet sein muss, dass es Lösungen geben muss, wie das, was mit fold*oder passiert map.

Bisher habe ich beim Lesen von learnyouahaskell.com keine gefunden, aber ich habe Monaden noch nicht angerührt.

( bei interesse habe ich meinen code auf codereview gepostet )

Funktionale Programmierung hebt den Zustand nicht auf. Es macht es nur deutlich! Funktionen wie map "enträtseln" zwar häufig eine "gemeinsam genutzte" Datenstruktur. Wenn Sie jedoch nur einen Erreichbarkeitsalgorithmus schreiben möchten, müssen Sie lediglich nachverfolgen, welche Knoten Sie bereits besucht haben:

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]

Jetzt muss ich gestehen, dass es ziemlich nervig und fehleranfällig ist, den Überblick über diesen Zustand von Hand zu behalten (es ist einfach, s 'anstelle von s' zu verwenden, es ist einfach, dasselbe s 'an mehr als eine Berechnung weiterzugeben ...) . Hier kommen Monaden ins Spiel: Sie fügen nichts hinzu, was Sie vorher noch nicht getan haben, aber sie lassen Sie die Zustandsvariable implizit weitergeben, und die Schnittstelle garantiert, dass dies in einer Singlethread-Weise geschieht.

Bearbeiten: Ich werde versuchen, eine genauere Begründung für das zu geben, was ich jetzt getan habe: Anstatt nur auf Erreichbarkeit zu testen, habe ich eine Tiefensuche codiert. Die Implementierung wird ziemlich gleich aussehen, aber das Debugging sieht ein bisschen besser aus.

In einer statusbehafteten Sprache würde die DFS ungefähr so ​​aussehen:

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)

Jetzt müssen wir einen Weg finden, den veränderlichen Zustand loszuwerden. Zuallererst werden wir die "visitlist" -Variable los, indem wir dafür sorgen, dass dfs das zurückgibt, anstatt dass es ungültig wird:

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

Und jetzt kommt der knifflige Teil: die "besuchte" Variable loszuwerden. Der grundlegende Trick besteht darin, eine Konvention zu verwenden, bei der der Status als zusätzlicher Parameter an Funktionen übergeben wird, die ihn benötigen, und diese Funktionen die neue Version des Status als zusätzlichen Rückgabewert zurückgeben, wenn sie ihn ändern möchten.

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

Um dieses Muster auf das dfs anzuwenden, müssen wir es ändern, um den Satz "visited" als zusätzlichen Parameter zu erhalten und die aktualisierte Version von "visited" als zusätzlichen Rückgabewert zurückzugeben. Außerdem müssen wir den Code neu schreiben, damit wir immer die "neueste" Version des "besuchten" Arrays weiterleiten:

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)

Die Haskell-Version macht so ziemlich das, was ich hier gemacht habe, außer dass sie den ganzen Weg geht und eine innere rekursive Funktion anstelle von veränderlichen "curr_visited" - und "childtrees" -Variablen verwendet.

Was Monaden betrifft, so ist das, was sie im Grunde erreichen, das implizite Weitergeben des "curr_visited", anstatt Sie zu zwingen, es von Hand zu tun. Dies beseitigt nicht nur die Unordnung im Code, sondern verhindert auch, dass Sie Fehler machen, z. B. beim Verzweigen des Status (Übergeben des gleichen "besuchten" Satzes an zwei aufeinanderfolgende Aufrufe, anstatt den Status zu verketten).

Hier ist eine einfache Antwort unter Berufung auf 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

Where neighborsgibt die Zustände zurück, die unmittelbar mit einem Zustand verbunden sind. Dies gibt eine Reihe von Pfaden zurück.