有没有办法重新present静态数据在Haskell？或者有没有其他的优雅算法在Haskell DFS遍历？ [英] Is there way to represent static data in Haskell? Or is there any other elegant algorithm for DFS traversal in Haskell?

问题描述

我想用递归算法来构建DFS树。

I am trying to construct DFS tree using recursive algorithm.

伪code因为这是：

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 /访问节点，赋予它们动态分配或某种声明，对哈斯克尔做到这一点在简单的方式势在必行的语言，这是不可能这样做，因为Haskell的纯净prevents我改变数据的同时传递参数。

While I can fairly easily accomplish this in imperative language in simple way by constructing some sort of data structure for un/visited nodes, assigning them dynamic allocation or some sort of declaration, for Haskell, it is impossible to do so since Haskell's pureness prevents me to change data while 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

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

This is what I've got for graph traversal using DFS-ish(or rather BFS-ish) algorithm but the problem is that it will visit all the points again that is not in points' path. (i.e if there exists a cycle, it will traverse in both ways clockwise and counter clockwise)

我也试着柯里另一个图形与参观点，但失败了，因为图形经过参数仅持有图表的数据在遍历（即不是全球）

I've also tried currying another Graph with visited points but failed since Graphs passed by parameter only holds data of Graph in the traversal (i.e is not global)

如果只动态分配或静态数据保存为全球范围内的数据是可能的，这可以很容易解决，但我有点新的Haskell和我找不到关于这个问题在网络上的答案。请帮我:(在此先感谢。

If only dynamic allocation or static data to hold data for global level was possible, this can be easily solved but I'm kinda new to Haskell and I couldn't find answers on the web on this issue. Please help me :( Thanks in advance.

（P.S） 我已经使用访问节点传递列表​​尝试，但没有奏效，因为当递归返回时，访问节点列表也将恢复，因此无法跟踪数据。如果有一种方法，使'地图'或'名单'全球性的，也可以实现这种方式。下面回答，尽管是一个链接唯一的答案，对为什么不能（或不应该）来实现的原因很好的解释。

(P.S) I've tried using passing list of visited nodes but it didn't work because when recursion returns, the list of visited nodes will also return, making it impossible to track data. If there is a way to make 'Map' or 'List' global, it is possible to implement it this way. Answer below despite is a link only answer, has great explanation on the reason why this can't be(or shouldn't be) implemented.

推荐答案

涉及传递和返回状态或使用状态单子比这种方法更透明，但提到在下面的文章的答案，它的效率不高，并没有按T推广好。在此回答说，无论您的需求，这是值得学习的状态单子和不可变的数据在Haskell工作。

The answer involving passing and returning state or using a state monad is more transparent than this approach, but as mentioned in the paper below, it's not as efficient and doesn't generalize well. That said, whatever your needs in this answer, it's worth learning about state monads and working with immutable data in Haskell.

在另一个答卷链接本文提供了使用的，而学术讨论所谓感性的图表。幸运的是，本文的作者是一种足以实现此方法作为一个Haskell库， FGL 。我要掩盖一些细节有关附加数据节点和诸如此类的东西，并展示如何使用这个库来实现DFS。可以很容易地修改这个算法产生的树，而不是列表，该列表的版本是显著更简洁。

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. I'm going to gloss over some details about attaching data to nodes and whatnot, and show how to implement DFS using this library. It's easy to modify this algorithm to produce trees instead of lists, and the list version is significantly more concise.

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

这里的关键是匹配，其分解图进入所谓的上下文 A顶点，其余图（比赛返回也许上下文，覆盖顶点的情况下没有在图中）。

The key here is match, which decomposes a graph into the so called Context of a vertex and the remaining graph (match returns a Maybe Context, to cover the case of a vertex not in the graph).

顶点上下文的概念是中央的感应图的想法：它定义为一个元组

The notion of a vertex Context is central to the idea of inductive graphs: it's defined as a tuple

(adjIn, nodeId, nodeLabel, adjOut)

其中， adjIn 和 adjOut 是的（edgeLabel，NODEID）名单对。

请注意的是，术语标签用于松散这里，和指连接到顶点或边一般数据

Note that the term label is used loosely here, and refers to general data attached to vertices or edges.

在 SUC函数获取上下文，并返回节点的节点在上下文接班人（名单<$ C C $> adjOut ，与边缘标签丢弃）。

The suc' function takes a context and returns a list of nodes that are successors of the node in the context (adjOut, with edge labels dropped).

我们可以建立这样的图

与code这样

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] 。

注：我很无聊，跨越这个问题迷迷糊糊的，所以答案是调查和实验的几个小时只是一个书面记录

Note: I was bored and stumbled across this question, so the answer is just a writeup of a couple hours of investigation and experiments.

这篇关于有没有办法重新present静态数据在Haskell？或者有没有其他的优雅算法在Haskell DFS遍历？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！