有没有办法在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)算法进行图遍历的问题,但问题是它将再次访问不在点路径中的所有点.(即如果存在循环,它将顺时针和逆时针两种方式移动)

我也试过用访问点来描述另一个图表,但由于参数传递的图表仅在遍历中保存Graph的数据(即不是全局的),因此失败了

如果只有动态分配或静态数据来保存全局级别的数据是可能的,这可以很容易地解决,但我对Haskell是个新手,我无法在网上找到关于这个问题的答案.请帮帮我:(先谢谢.

(PS)我尝试使用传递的访问节点列表,但它没有工作,因为当递归返回时,访问节点列表也将返回,从而无法跟踪数据.如果有办法使"地图"或"列表"全局化,则可以通过这种方式实现它.尽管只是一个链接答案,下面的答案,对于不能(或不应该)实施的原因有很好的解释.

Answer 1

涉及传递和返回状态或使用状态monad的答案比这种方法更透明,但如下文所述,它不是那么有效且不能很好地概括.也就是说,无论你在这个答案中需要什么,都值得学习状态monad并在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的顶点和剩余的图形(匹配返回a Maybe 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 testGraph产生[1,3,4,5,2].

注意:我很无聊并偶然发现了这个问题,所以答案只是几个小时的调查和实验.