我开始怀疑我的Haskell和函数编程的计划是否通过使用Haskell进行我的下一个算法课程是一个很好的计划.
为了得到一些Haskell线,我开始尝试实现一些简单的算法.第一:稳定婚姻问题的Gale-Shapley.尚未进入monad,所有可变状态看起来令人生畏,所以我使用稳定匹配的表征作为半匹配点阵上映射的固定点.它很有趣,但它不再是Gale-Shapley而且复杂性不是很好(晶格中的那些链条显然可以很长:)
接下来我有平面中最近点对的算法,但是我坚持得到通常的O(n*log n)复杂度,因为我无法弄清楚如何用O(1)获得类似于集合的数据结构)检查会员资格.
所以我的问题是:一般可以实现大多数算法,例如.Dijkstra,Ford-Fulkerson(Gale-Shapley!？)如果能更好地掌握Haskell和函数式编程,那么从程序实现中获得复杂性？
C. *_*ann 15
这一般可能无法回答.许多标准算法是围绕可变性设计的,并且在某些情况下存在翻译,而在其他情况下则不存在.有时存在具有相同性能特征的替代算法,有时您确实需要可变性.
如果您想了解如何在此设置中处理算法,那么一个好的起点是Chris Okasaki的书Purely Functional Data Structures.这本书是他论文的扩展版本,可以在线获得PDF格式.
如果你需要特定算法的帮助,比如O(1)成员资格检查(这实际上是误导性的 - 没有这样的东西,这样的数据结构通常有类似O(k)的东西,其中k是存储元素的大小)你最好把它作为一个特定的单一问题,而不是像这样的一般性问题.