首先,我是Haskell的新手。我读了这篇文章:高度可变领域中的不可变函数对象。我的问题几乎与此相同——如何有效地编写需要更改状态的算法。以Dijkstra算法为例,新路径将被发现,并且距离应该被更新。在传统语言中,这很简单,而在Haskell中,我只能想到创建完全新的距离,这将太慢且占用内存。是否有像设计模式这样的东西,可以在可变数据结构下实现算法,并且速度和内存使用是主要问题?
首先,我是Haskell的新手。我读了这篇文章:高度可变领域中的不可变函数对象。我的问题几乎与此相同——如何有效地编写需要更改状态的算法。以Dijkstra算法为例,新路径将被发现,并且距离应该被更新。在传统语言中,这很简单,而在Haskell中,我只能想到创建完全新的距离,这将太慢且占用内存。是否有像设计模式这样的东西,可以在可变数据结构下实现算法,并且速度和内存使用是主要问题?
当然,函数式语言解决这个问题的方法有很多。
不同的数据结构 - 许多数据结构可以以纯函数式的方式实现,具有与命令式版本相同的算法复杂度。这个领域中最著名的工作可能是Chris Okasaki的Purely Functional Data Structures,但还有许多其他资源可用。对于Dijkstra算法,Martin Erwig在functional graphs上的工作很合适。也可以参考此问题。
不同的算法 - 一些算法内置了可变性的假设,快速排序就是其中之一。在这种情况下,可以使用更适合于不可变性的替代算法。
可变状态 - 每个函数式语言都可以使用State monad来模拟函数式状态。大多数还提供其他形式的可变性,例如Haskell的ST monad和IORef's。
创建新的不可变对象并不像你想象的那么昂贵,因为编译器知道它们不能改变,所以可以安全地共享大量的结构。尽管如此,在Haskell中使用高度命令式的算法和大量可变状态是一种代码异味。