Gibt es eine Möglichkeit, statische Daten in Haskell darzustellen? Oder gibt es einen anderen eleganten Algorithmus für das DFS-Traversal in Haskell?

Question

Ich versuche, DFS-Baum mit rekursiven Algorithmus zu erstellen.

Pseudo-Code hierfür lautet:

DFF(G) 
Mark all nodes u as unvisited 
while there is an unvisited node u do 
    DFS(u) 

.

DFS(u) 
Mark u as visited 
for each v in u's neighbor do 
    if v is not marked 
     DFS(v) 

Während ich kann ziemlich leicht dies in einfacher Weise in imperativen Sprache zu erreichen, indem eine Art von Datenstruktur für un/besuchten Knoten konstruieren, so dass sie die dynamische Zuordnung oder irgendeine Art von Erklärung, für Haskell zuweisen, es ist unmöglich, tun Sie es, weil Haskells Reinheit mich daran hindert, Daten zu ändern, während ich Parameter übergebe.

data Graph a = Graph [(a,[a])] deriving (Ord, Eq, Show) 
data Tree a = Node a [Tree a] deriving (Ord, Eq, Show) 

type Point = (Int, Int) 
type Edges = [Point] 
type Path = [Point] 

pathGraphFy :: Graph Point -> Point -> Tree (Point,Path) 
pathGraphFy inputGraph point = getPathVertex inputGraph (point,[]) 

getPathVertex :: Graph Point -> (Point, Path) -> Tree (Point,Path) 
getPathVertex inputGraph (point,path) = 
    Node (point,point:path) (map (getPathVertex inputGraph) [(x,(point:path)) | x<- neighbors, x `notElem` path]) 
    where neighbors = pointNeighbor inputGraph point 

pointNeighbor :: Graph Point -> Point -> Edges 
pointNeighbor (Graph (x:xs)) point = 
    if fst x == point then snd x else pointNeighbor (Graph(xs)) point 

Dies ist, was ich für Graph Traversal mit der DFS-ish (oder eher BFS-ish) Algorithmus haben aber das Problem ist, dass es wieder alle Punkte besuchen in den Punkten Weg ist das nicht. (dh wenn es einen Zyklus gibt, wird er auf beide Arten im Uhrzeigersinn und gegen den Uhrzeigersinn verfahren)

Ich habe auch versucht, einen anderen Graph mit besuchten Punkten zu currying, da Graphs passed by parameters nur Daten von Graph im Traversal enthält ((dh ist nicht global)

Wenn nur dynamische Zuordnung oder statische Daten zu Daten für globale Ebene möglich war, kann dies leicht gelöst werden, aber ich bin etwas neu zu Haskell und ich konnte keine Antworten im Internet finden Problem. Bitte helfen Sie mir :(Vielen Dank im Voraus.

(PS) Ich habe versucht mit der Weitergabe Liste der besuchten Knoten, aber es hat nicht funktioniert, weil bei Rekursion zurückkehrt, wird die Liste der besuchten Knoten auch zurückkehren, so dass es unmöglich um Daten zu verfolgen.Wenn es eine Möglichkeit gibt, 'Karte' oder 'Liste' global zu machen, ist es möglich, es auf diese Art zu implementieren. Die Antwort unten ist trotz einer Link-nur-Antwort, hat eine große Erklärung dafür, warum dies nicht sein kann (oder sollte nicht) implementiert

Answer 1

Die Antwort beteiligt vorbei und Rückkehrzustand oder mit einem Zustand Monade als dieser Ansatz mehr transparent ist, sondern, wie unten in dem Papier erwähnt, es ist nicht so effizient und verallgemeinert sich nicht gut. Nichtsdestoweniger lohnt es sich, in dieser Antwort über staatliche Monaden zu lernen und mit unveränderlichen Daten in Haskell zu arbeiten.

The paper linked in another Antwort Papier bietet eine eher akademische Diskussion über die Verwendung von sogenannten induktiven Graphen. Glücklicherweise war der Autor des Artikels so freundlich, diesen Ansatz als Haskell-Bibliothek zu implementieren, fgl. Ich werde einige Details über das Anfügen von Daten an Knoten und was sonst noch beschönigen und zeigen, wie man DFS mit dieser Bibliothek implementiert. Es ist einfach, diesen Algorithmus zu ändern, um Bäume anstelle von Listen zu erstellen, und die Listenversion ist deutlich prägnanter.

dfs :: Graph gr => [Node] -> gr a b -> [Node] 
dfs [] _ = [] 
-- this equation isn't strictly necessary, but it can improve performance for very dense graphs. 
dfs _ g | isEmpty g = [] 
dfs (v:vs) g = case match v g of 
    (Just ctx, g') -> v:dfs (suc' ctx ++ vs) g' 
    _ -> dfs vs g 

Der Schlüssel ist hier match, die Context einen Scheitel und die verbleibenden Graphen, der eine grafische Darstellung, in die so genannten zersetzt (Match liefert ein Maybe Context, den Fall eines Scheitel zu bedecken nicht in der Grafik).

Der Begriff eines Scheitels ist Context auf die Idee der induktiven Graphen zentral: es als Tupel

(adjIn, nodeId, nodeLabel, adjOut) 

definiert ist, wo adjIn und adjOut Listen (edgeLabel, nodeId) Paare sind.

Beachten Sie, dass der Begriff Label hier lose verwendet wird und sich auf allgemeine Daten bezieht, die an Scheitelpunkte oder Kanten angehängt sind.

Die Funktion suc' nimmt einen Kontext und gibt eine Liste der Knoten zurück, die Nachfolger des Knotens im Kontext sind (adjOut, mit entfernten Kantenbeschriftungen).

Wir können eine grafische Darstellung wie diese

mit Code wie diesem dfs testGraph erzeugt [1,3,4,5,2] Aufruf

testGraph :: DynGraph g => gr a b 
testGraph = 
    let nodes = [(i, "N" ++ show i) | i <- [1..5]] 
     edges = [(2,1,"E21") 
       ,(4,1, "E41") 
       ,(1,3, "E13") 
       ,(3,4, "E34") 
       ,(3,5,"E35") 
       ,(5,2, "E52")] 
     withNodes = insNodes nodes empty 
     in insEdges edges withNodes 

bauen.

Hinweis: Ich war gelangweilt und stolperte über diese Frage, also ist die Antwort nur eine Zusammenfassung von ein paar Stunden von Untersuchungen und Experimenten.

Answer 2

Nichts, was Sie hält von dem Zustand kodiert, in Funktionsargumente/Rückgabewerte Ein klassisches DFS könnte wie folgt aussehen:..

import qualified Data.Map as Map 
import qualified Data.Set as Set 

newtype Graph a = Graph (Map.Map a [a]) deriving (Ord, Eq, Show) 
data Tree a = Tree a [Tree a] deriving (Ord, Eq, Show) 

dfs :: (Ord a) => Graph a -> a -> Tree a 
dfs (Graph adj) start = fst $ dfs' (Set.singleton start) start 
    where 
    neighbors x = Map.findWithDefault [] x adj 
    dfs' vis x = 
     let (subtrees, vis') = 
      foldr 
       (\y (subtrees, vis) -> 
       if Set.member y vis 
        then (subtrees, vis) 
        else let vis' = Set.insert y vis 
          (t, vis'') = dfs' vis' y 
         in (t : subtrees, vis'') 
      ) 
       ([], vis) 
       (neighbors x) 
     in (Tree x subtrees, vis') 

Anstelle von Map/Set können Sie je nach Knotentyp auch persistent hash tables oder integer maps/sets verwenden.

den expliziten Zustand zu vermeiden, können Sie eine state monad verwenden sollen:

import Control.Applicative 
import Control.Monad.State 
import Control.Monad 
import Data.Maybe 
{- ... -} 

dfs :: (Ord a) => Graph a -> a -> Tree a 
dfs (Graph adj) start = evalState (dfs' start) (Set.singleton start) 
    where 
    neighbors x = Map.findWithDefault [] x adj 
    dfs' x = Tree x . catMaybes <$> 
     forM (neighbors x) (\y -> get >>= \vis -> 
     if Set.member y vis 
      then return Nothing 
      else put (Set.insert y vis) >> Just <$> dfs' y)