功能拓扑排序

Question

在拓扑排序算法中,我们执行DFS并在遇到它们时将节点推送到链表.我可以想到在功能上执行此操作的唯一方法是将列表作为参数传递给调用,这是丑陋且非常低效的(即,它显示在大O中,因为复制列表是O(n).如何在Haskell中以惯用方式执行此操作？

Answer 1

该FGL本文讨论的是如何做图形算法以多功能风格的第一个例子就这个问题询问:

dfs :: [Node] -> Graph a b -> [Node]
dfs []     g        = []
dfs (v:vs) (c &v g) = v:dfs (suc c++vs) g
dfs (v:vs) g        = dfs vs g

[编者注:c &v g本文前面介绍的符号是一种"图形上的模式匹配":c &v g匹配包含顶点的图形v,绑定c到上下文中的边缘和边界外的边缘以及g带有该节点的图形它的边缘删除了.在Haskell库中,这是通过函数实现的match.]

该算法的工作原理如下.如果没有剩余的节点要访问(第一种情况),则dfs停止而不返回任何节点.相反,如果仍有必须访问的节点,则dfs尝试v在参数图中找到第一个节点()的上下文.如果这是可能的(第二个等式),即v参数图中包含的情况,v则是结果节点列表中的下一个节点,并且继续搜索剩余图表g,其余的图表v将在剩余列表之前被访问的节点vs.将后继者放在所有其他节点之前的事实导致dfs在深度而不是广度上进行搜索.最后,如果v无法匹配(最后一行),则dfs继续使用剩余的节点列表进行搜索vs.请注意,最后一种情况只有v在图形中不包含时才会出现,否则第二个等式中的模式将匹配.

由于复制和粘贴工作不正常,我不得不转录此文本; 任何拼写错误几乎都是我的,而不是Martin Erwig.

如您所知,剩下要访问的节点列表作为参数传入.但是,你声称效率低下似乎对我不利; 构建新列表的成本suc c++vs是O(length (suc c)) - 但是你必须至少访问所有这些节点才能完成深度优先搜索,这样渐近的成本是不可避免的.

上面链接的全文花了很多时间讨论渐近和效率,并且(在我看来)也很有启发性,所以我鼓励你读一读.