有没有办法在Haskell中表示静态数据？或者在Haskell中还有其他优雅的DFS遍历算法吗？

Question

我正在尝试使用递归算法构造DFS树。

这个的伪代码是：

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)

虽然通过为未访问/访问的节点构造某种数据结构、为它们分配动态分配或某种声明，我可以用命令式语言以简单的方式很容易地实现这一点，但对于Haskell来说，这是不可能的，因为Haskell的纯净性使我无法在传递参数时更改数据。

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

这是我使用DFS ish（或者更确切地说是BFS ish）算法进行图形遍历时得到的结果，但问题是它将再次访问不在点路径中的所有点。（即，如果存在一个循环，它将以顺时针和逆时针两种方式移动）

我也尝试过用访问点来处理另一个图，但失败了，因为通过参数传递的图只保存遍历中的图的数据（即不是全局的）

如果只有动态分配或静态数据来保存全局级别的数据是可能的，这可以很容易地解决，但我对Haskell有点陌生，我无法在web上找到关于这个问题的答案。请帮帮我：（提前谢谢。

（P. S）我尝试过使用访问节点的传递列表，但它不起作用，因为当递归返回时，访问节点的列表也会返回，使得无法跟踪数据。如果有一种方法可以使地图或列表全局化，那么可以这样实现它。尽管下面的答案是一个链接唯一的答案，但它对为什么不能（或不应该）实施有很好的解释。

Answer 1

没有任何东西可以阻止您在函数参数/返回值中编码状态。经典的DFS可能如下所示：

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

除了Map/Set，还可以使用持久哈希表或整数映射/集，具体取决于节点类型。

为了避免显式状态，您应该使用状态单子：

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)

Answer 2

涉及传递和返回状态或使用状态单子的答案比这种方法更加透明，但正如下面的文章所提到的，这种方法效率不高，也不能很好地推广。也就是说，无论您在这个答案中需要什么，都值得学习状态单子并在Haskell中使用不可变数据。

另一篇答题论文中的论文对所谓归纳图的使用进行了相当学术性的讨论。幸运的是，本文作者非常友好地将此方法实现为Haskell库，fgl。我将介绍一些关于将数据附加到节点等的细节，并展示如何使用此库实现DFS。修改此算法以生成树而不是列表很容易，而且列表版本更简洁。

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

这里的关键是match，它将一个图分解为一个顶点的所谓Context，剩下的图（match返回一个可能是Context，以覆盖不在图中的顶点的情况）。

顶点Context的概念是归纳图的核心：它被定义为元组

(adjIn, nodeId, nodeLabel, adjOut)

其中adjIn和adjOut是（edgeLabel，nodeId）对的列表。

请注意，此处使用的术语标签比较松散，指附加到顶点或边的常规数据。

suc'函数获取一个上下文并返回一个节点列表，这些节点是上下文中该节点的后续节点（adjOut，删除边标签）。

我们可以建立这样的图表

用这样的代码

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

调用dfs testGgraph生成[1,3,4,5,2]。

注：我很无聊，偶然发现了这个问题，所以答案只是写了几个小时的调查和实验。