基本上，我知道如何创建图形数据结构并在允许副作用的编程语言中使用 Dijkstra 算法。通常，图算法使用一种结构将某些节点标记为“已访问”，但这会产生副作用，这是我试图避免的。
我可以想到一种用函数式语言来实现这一点的方法，但它基本上需要将大量状态传递给不同的函数，我想知道是否有更节省空间的解决方案。
最佳答案
您可以查看 Martin Erwig 的 Haskell functional graph library 是如何实现的做事。例如，它的shortest-path functions都是纯的，可以看到source code了解它是如何实现的。
另一个选项，like fmark mentioned ，就是使用一种抽象，允许您根据状态实现纯函数。他提到了 State monad(有 lazy 和 strict 两种类型)。另一种选择，如果您使用 GHC Haskell 编译器/解释器(或者我认为任何支持 2 级类型的 Haskell 实现)，另一种选择是 the ST monad ，它允许您编写在内部处理可变变量的纯函数。
关于functional-programming - 如何用函数式编程语言实现图和图算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2999072/