Funktionale Programmierung und zustandsbehaftete Algorithmen

12

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 :

Digraphen, der einen Automaten darstellt

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 )

Bigstones
quelle
3
Zum einen würde ich gerne den Code sehen, mit dem Sie versucht haben, zu arbeiten. In Ermangelung dessen ist mein bester Rat, dass Haskells Faulheit oft ausgenutzt werden kann, um Dinge nicht mehr als einmal zu berechnen. Schauen Sie sich die sogenannte "Knotenbindung" und die träge Wertrekursion an, obwohl Ihr Problem wahrscheinlich so einfach ist, dass die fortgeschritteneren Techniken, die unendliche Werte und ähnliche Dinge ausnutzen, übertrieben wären und Sie wahrscheinlich gerade verwirren würden.
Pthariens Flamme
1
@ Ptharien'sFlame danke für dein Interesse! Hier ist der Code , es gibt auch einen Link zum gesamten Projekt. Ich bin schon verwirrt mit dem, was ich bisher gemacht habe, also ja, besser nicht in fortgeschrittene Techniken schauen :)
bigstones
1
Ein Zustandsautomat ist so ziemlich das Gegenteil von funktionaler Programmierung. Bei der funktionalen Programmierung geht es darum, Probleme ohne internen Zustand zu lösen, während es bei Zustandsautomaten ausschließlich um die Verwaltung eines eigenen Zustands geht.
Philipp
@Philipp Ich bin anderer Meinung. Ein Automat oder eine Zustandsmaschine ist manchmal die natürlichste und genaueste Art, ein Problem darzustellen, und funktionale Automaten sind gut untersucht.
Pthariens Flamme
5
@Philipp: Beim funktionalen Programmieren geht es darum, Zustände explizit zu machen, nicht darum, sie zu verbieten. Tatsächlich ist die Schwanzrekursion ein großartiges Werkzeug für die Implementierung von Zustandsautomaten voller GOTOS.
Hugomg

Antworten:

16

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

hugomg
quelle
Ich wusste, dass es eine Möglichkeit geben musste, es weniger schmerzhaft und vielleicht besser lesbar zu machen, weil ich Schwierigkeiten habe, Ihr Beispiel zu verstehen. Soll ich mich für Monaden entscheiden oder besser üben, um Code wie Ihren zu verstehen?
Bigstones
@bigstones: Ich denke, Sie sollten versuchen, zu verstehen, wie mein Code funktioniert, bevor Sie sich mit Monaden befassen. Sie werden im Grunde das Gleiche tun, was ich getan habe, aber mit zusätzlichen Abstraktionsebenen, um Sie zu verwirren. Wie auch immer, ich habe einige zusätzliche Erklärungen hinzugefügt, um die Dinge ein bisschen klarer zu machen
hugomg
1
"Funktionale Programmierung wird den Zustand nicht los. Sie macht ihn nur explizit!": Das ist wirklich klarstellend!
Giorgio
"Mit [Monaden] können Sie die Zustandsvariable implizit weitergeben, und die Schnittstelle stellt sicher, dass dies auf Singlethread-Weise geschieht." <- Dies ist eine anschauliche Beschreibung der Monaden. außerhalb des kontexts dieser frage kann ich die 'state variable' durch 'closure' ersetzen
anthropic android
2

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.

Daniel Gratzer
quelle