可变性的函数式编程 [英] Mutability in functional programming

问题描述

首先我是一个Haskell新手。 我读过这样的： <一href="http://stackoverflow.com/questions/166379/immutable-functional-objects-in-highly-mutable-domain">Immutable在高度可变域功能对象 我的问题是几乎相同的 - 如何高效地编写算法，其状态应该改变。让我们举个例子Dijkstra算法。将会有新的途径发现和距离应更新。而在传统的语言，这是简单的，而在Haskell比如我只能想创造全新的距离，这将是太慢，内存消耗的。是否有类似的设计模式，其中一个应该实现算法，可变数据结构，速度和内存使用此类案件主要关注？

First I am a Haskell newbie. I've read this: Immutable functional objects in highly mutable domain And my question is nearly the same -- how to efficiently write algorithms where the state is supposed to change. Let's take for example Dijkstra's algorithm. There will be new paths found and distances should be updated. And in traditional languages this is simple while in Haskell for example I can only think of creating entirely new distances which will be too slow and memory consuming. Are there something like design patterns for such cases where one should implement algorithm with mutable data structure and speed and memory usage are main concerns?

推荐答案

当然也有很多方法函数式语言解决这个问题。

There are of course many ways functional languages address this issue.

1. 不同的数据结构 - 的许多数据结构能够在一个的纯功能的方式来实施，使用相同的算法的复杂性作为必要的版本。也许在这一领域的最知名的作品是克里斯Okasaki的纯功能性数据结构，但也有很多其他的资源。对于Dijkstra算法，马丁Erw​​ig 的上的功能图是合适的。请参阅<一href="http://stackoverflow.com/questions/2999072/how-do-i-implement-graphs-and-graph-algorithms-in-a-functional-programming-langua">this问题也是如此。

1. Different data structures - many data structures can be implemented in a purely functional manner, with the same algorithmic complexity as imperative versions. Probably the most well-known work in this area is Chris Okasaki's Purely Functional Data Structures, but there are many other resources as well. For Dijkstra's algorithm, Martin Erwig's work on functional graphs is appropriate. See this question as well.

不同的算法 - 一些算法具有可变性内置的假设，快速排序是这样的一个例子。在这种情况下，另一种算法，可用于这更适于不变性

Different algorithms - some algorithms have assumptions of mutability built-in, Quicksort is an example of this. In this case an alternative algorithm can be used that's more amenable to immutability.

可变状态 - 每一个功能性的语言可以用一个国家的单子建模功能状态。大多数提供其他形式的可变性，以及，如Haskell的ST单子和IOREF的。

Mutable state - every functional language can model functional state with a State monad. Most provide other forms of mutability as well, such as Haskell's ST monad and IORef's.

这篇关于可变性的函数式编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！