Mar*_*riy 15 algorithm haskell functional-programming data-structures
首先,我是一名Haskell新手.我读过这个: 高度可变域中的不可变功能对象 我的问题几乎相同 - 如何有效地编写状态应该改变的算法.让我们以Dijkstra的算法为例.将找到新路径并更新距离.在传统语言中,这很简单,而在Haskell中,例如我只能想到创建全新的距离,这些距离太慢而且占用内存.是否存在类似于设计模式的情况,其中应该实现具有可变数据结构的算法,并且速度和内存使用是主要问题？
Joh*_*n L 19
功能语言当然有很多方法可以解决这个问题.
不同的数据结构 - 许多数据结构可以以纯函数方式实现,具有与命令式版本相同的算法复杂性.该领域最着名的作品可能是Chris Okasaki的纯功能数据结构,但也有许多其他资源.对于Dijkstra的算法,Martin Erwig关于函数图的研究是恰当的.也看到这个问题.
不同的算法 - 一些算法内置可变性的假设,Quicksort就是这样的一个例子.在这种情况下,可以使用更适合不变性的替代算法.
可变状态 - 每种功能语言都可以使用State monad对功能状态进行建模.大多数还提供其他形式的可变性,例如Haskell的ST monad和IORef's.
创建新的不可变对象并不像您想象的那样费用,因为可能会发生大量的结构共享,因为编译器知道它们无法更改,因此可以安全地共享.也就是说,在Haskell中使用具有大量可变状态的高命令性算法是一种代码味道.