如何用函数式编程语言实现图和图算法？

发布于 2024-09-04 08:06:18 字数 166 浏览 5 评论 0 原文

基本上，我知道如何创建图形数据结构并在允许副作用的编程语言中使用 Dijkstra 算法。通常，图算法使用一种结构将某些节点标记为“已访问”，但这会产生副作用，这是我试图避免的。

我可以想到一种用函数式语言实现这一点的方法，但它基本上需要将大量状态传递给不同的函数，我想知道是否有更节省空间的解决方案。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

呆头 2024-09-11 08:06:18

您可以查看 Martin Erwig 的 Haskell 函数图形库是如何工作的。例如，其最短路径函数都是纯粹的，你可以看到源代码了解其实现方式。

另一种选择，就像提到的 fmark 一样，是使用一个抽象，它允许您根据状态实现纯函数。他提到了 State monad（在惰性和严格品种）。另一种选择，如果您使用 GHC Haskell 编译器/解释器（或者我认为任何支持 2 级类型的 Haskell 实现），另一种选择是 ST monad，它允许您编写处理可变变量的纯函数内部。

回复收藏 0 原文

爱她像谁 2024-09-11 08:06:18

我只是将访问的集合保留为一个集合并将其作为参数传递。任何有序类型的集合和超高效整数集合都有有效的日志时间实现。

为了表示图，我使用邻接列表，或者使用有限映射将每个节点映射到其后继列表。这取决于我想做什么。

我推荐 Chris Okasaki 的 纯函数式数据结构，而不是 Abelson 和 Sussman 。我已经链接到克里斯的论文，但如果你有钱，他将其扩展为很棒的书。

只是为了一笑，这里有一个有点可怕的反向后序深度优先搜索，在 Haskell 中以连续传递的方式完成。这直接来自 Hoopl 优化器库：

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e)
                          => LabelMap (block C C) -> e -> LabelSet -> [block C C]
postorder_dfs_from_except blocks b visited =
 vchildren (get_children b) (\acc _visited -> acc) [] visited
 where
   vnode :: block C C -> ([block C C] -> LabelSet -> a) 
                      -> ([block C C] -> LabelSet -> a)
   vnode block cont acc visited =
        if setMember id visited then
            cont acc visited
        else
            let cont' acc visited = cont (block:acc) visited in
            vchildren (get_children block) cont' acc (setInsert id     visited)
      where id = entryLabel block
   vchildren bs cont acc visited = next bs acc visited
      where next children acc visited =
                case children of []     -> cont acc visited
                                 (b:bs) -> vnode b (next bs) acc     visited
   get_children block = foldr add_id [] $ targetLabels bloc
   add_id id rst = case lookupFact id blocks of
                      Just b -> b : rst
                      Nothing -> rst

I just keep the visited set as a set and pass it as a parameter. There are efficient log-time implementations of sets of any ordered type and extra-efficient sets of integers.

To represent a graph I use adjacency lists, or I'll use a finite map that maps each node to a list of its successors. It depends what I want to do.

Rather than Abelson and Sussman, I recommend Chris Okasaki's Purely Functional Data Structures. I've linked to Chris's dissertation, but if you have the money, he expanded it into an excellent book.

Just for grins, here's a slightly scary reverse postorder depth-first search done in continuation-passing style in Haskell. This is straight out of the Hoopl optimizer library:

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e)
                          => LabelMap (block C C) -> e -> LabelSet -> [block C C]
postorder_dfs_from_except blocks b visited =
 vchildren (get_children b) (\acc _visited -> acc) [] visited
 where
   vnode :: block C C -> ([block C C] -> LabelSet -> a) 
                      -> ([block C C] -> LabelSet -> a)
   vnode block cont acc visited =
        if setMember id visited then
            cont acc visited
        else
            let cont' acc visited = cont (block:acc) visited in
            vchildren (get_children block) cont' acc (setInsert id     visited)
      where id = entryLabel block
   vchildren bs cont acc visited = next bs acc visited
      where next children acc visited =
                case children of []     -> cont acc visited
                                 (b:bs) -> vnode b (next bs) acc     visited
   get_children block = foldr add_id [] $ targetLabels bloc
   add_id id rst = case lookupFact id blocks of
                      Just b -> b : rst
                      Nothing -> rst

回复收藏 0 原文