有没有办法在 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)

虽然我可以通过为 un/visited 节点构建某种数据结构，为它们分配动态分配或某种声明，以简单的方式用命令式语言以简单的方式轻松完成此操作，但对于 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 有点陌生，我无法在网上找到这方面的答案问题。请帮助我 :( 提前致谢。

(P.S) 我试过使用已访问节点的传递列表，但它没有用，因为当递归 returns 时，已访问节点列表也将 return，从而无法跟踪数据。如果有办法使 'Map' 或 'List' 全局化，则可以通过这种方式实现。下面的答案尽管是 link 唯一的答案，但对为什么不能（或不应该）实施的原因有很好的解释。

Answer 1

没有什么能阻止您在函数 arguments/return 值中编码状态。经典的 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，您还可以使用 persistent hash tables or integer maps/sets，具体取决于您的节点类型。

为避免显式状态，您应该使用 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)

Answer 2

涉及传递和返回状态或使用状态 monad 的答案比这种方法更透明，但正如下面的论文中提到的那样，它效率不高并且不能很好地概括。也就是说，无论您对此答案有何需求，都值得了解状态单子并在 Haskell.

中使用不可变数据

The paper linked in another answer paper provides a rather academic discussion of the use of so called inductive graphs. Fortunately, the author of the paper was kind enough to implement this approach as a Haskell library, 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一个顶点和剩下的图（匹配returns一个Maybe Context，到覆盖不在图中的顶点的情况）。

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

(adjIn, nodeId, nodeLabel, adjOut)

其中 adjIn 和 adjOut 是 (edgeLabel, nodeId) 对的列表。

请注意，术语标签在这里使用不严格，指的是附加到顶点或边的一般数据。

suc' 函数采用一个上下文和 returns 一个节点列表，这些节点是上下文中节点的后继节点（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 testGraph 产生 [1,3,4,5,2].

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

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

Is there way to represent static data in Haskell? Or is there any other elegant algorithm for DFS traversal in Haskell?

algorithm

haskell

depth-first-search