Is there a way to present static data in Haskell? Or is there another elegant DFS bypass algorithm in Haskell?

Question

I am trying to build a DFS tree using a recursive algorithm.

Pseudo code for this:

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 neighbor do if v is not marked DFS(v) 

Although I can quite easily do this in an imperative language in a simple way, by building some kind of data structure for un / visited nodes, assigning them dynamic allocation or some kind of declaration for Haskell, this cannot be done since Haskell's purity prevents me from changing data when passing parameters.

 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 

This is what I have to bypass the graph using the DFS-ish algorithm (or rather BFS-ish), but the problem is that it will again visit all the points that are not in the waypoints. (i.e. if there is a cycle, it will go in both directions clockwise and counterclockwise)

I also tried to curry another Graph with the visited points, but it didn’t work, since the graphs passed by the parameter contain only Graph data bypassing (i.e. not global)

If only dynamic allocation or static data is possible to store data for the global level, this can be easily solved, but I am new to Haskell and I could not find answers on the Internet on this issue. Please help me :( Thanks in advance.

(PS) I tried using the passing list of visited nodes, but it did not work, because when the recursion returns, the list of visited nodes will also return, which will make it impossible to track data. If there is a way to make "Map" or "List" global, you can implement it this way. The answer below, despite the fact that this is an answer only to a link, has a great explanation for the reason why it cannot be (or should not be) implemented.

Answer 1

The answer related to the transfer and return of the state or the use of the state monad is more transparent than this approach, but, as mentioned in the article below, it is not so effective and does not generalize well. However, regardless of your needs for this answer, it's worth learning about state monads and working with immutable data in Haskell.

A document linked in another document gives a rather academic discussion of the use of so-called inductive graphs. Fortunately, the author of the article was kind enough to implement this approach as the Haskell library, fgl . I am going to hush up some details about attaching data to nodes and a lot, and also show how to implement DFS using this library. It is easy to modify this algorithm to create trees instead of lists, and the list version is much shorter.

 dfs :: Graph gr => [Node] -> gr ab -> [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 vg of (Just ctx, g') -> v:dfs (suc' ctx ++ vs) g' _ -> dfs vs g 

The key here is match , which breaks the graph into the so-called Context vertices, and the remaining graph (a match returns a Maybe Context to cover the case of a vertex that is not on the graph).

The concept of the vertex Context is central to the idea of ​​inductive graphs: it is defined as a set

 (adjIn, nodeId, nodeLabel, adjOut) 

where adjIn and adjOut are lists of pairs (edgeLabel, nodeId) .

Please note that the term label is used here freely and refers to general data attached to vertices or edges.

The suc' function takes a context and returns a list of nodes that are the successors of the node in the context ( adjOut when label labels are omitted).

We can build such a graph

with code like this

 testGraph :: DynGraph g => gr ab 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 

The dfs testGraph call dfs testGraph calls [1,3,4,5,2] .

Note: I was bored and stumbled upon this question, so the answer is just a record of several hours of research and experimentation.

Answer 2

Nothing prevents you from encoding state in function arguments / return values. Classic DFS might look like this:

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

Instead of Map/Set you can also use persistent hash tables or integer maps / sets , depending on your node type.

To avoid an explicit state, you should use the state monad :

 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)