bra*_*rad 44 computer-science functional-programming graph
基本上,我知道如何创建图形数据结构,并在允许副作用的编程语言中使用Dijkstra算法.通常,图算法使用一种结构将某些节点标记为"已访问",但这有副作用,我试图避免这种情况.
我可以想到一种在函数式语言中实现它的方法,但它基本上需要将大量的状态传递给不同的函数,我想知道是否有更节省空间的解决方案.
Ant*_*sky 17
您可以查看Martin Erwig的Haskell 功能图库是如何完成的.例如,它的最短路径功能都是纯粹的,您可以看到它的实现方式的源代码.
另一个选项,如fmark所提到的,是使用一个抽象,它允许你在状态方面实现纯函数.他提到国家monad(有懒惰和严格的品种).另一个选择,如果你在GHC Haskell编译器/解释器(或者,我认为,任何支持rank-2类型的Haskell实现)中工作,另一个选项是ST monad,它允许你编写处理mutable的纯函数内部变量.