如何在函数式编程语言中实现图形和图形算法？ [英] How do I implement graphs and graph algorithms in a functional programming language?

问题描述

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

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

解决方案

您可以查看Martin Erwig的Haskell 功能图库会做一些事情。例如，它的最短路径函数都是纯粹的，你可以看到源代码，以了解它的实现方式。 另外一个选项 like fmark mentioned ，就是使用一个抽象，它允许你在状态方面实现纯函数。他提到了国家monad（可以在懒惰和 strict 品种）。另一种选择是，如果你在GHC Haskell编译器/解释器（或者我认为，任何支持rank-2类型的Haskell实现）中工作，另一个选择是 ST monad ，它允许你编写处理可变的纯函数内部变量。

Basically, I know how to create graph data structures and use Dijkstra's algorithm in programming languages where side effects are allowed. Typically, graph algorithms use a structure to mark certain nodes as 'visited', but this has side effects, which I'm trying to avoid.

I can think of one way to implement this in a functional language, but it basically requires passing around large amounts of state to different functions, and I'm wondering if there is a more space-efficient solution.

解决方案

You might check out how Martin Erwig's Haskell functional graph library does things. For instance, its shortest-path functions are all pure, and you can see the source code for how it's implemented.

Another option, like fmark mentioned, is to use an abstraction which allows you to implement pure functions in terms of state. He mentions the State monad (which is available in both lazy and strict varieties). Another option, if you're working in the GHC Haskell compiler/interpreter (or, I think, any Haskell implementation which supports rank-2 types), another option is the ST monad, which allows you to write pure functions which deal with mutable variables internally.

这篇关于如何在函数式编程语言中实现图形和图形算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！