基本上,我知道如何创建图形数据结构,并在允许副作用的编程语言中使用Dijkstra算法.通常,图算法使用一种结构将某些节点标记为"已访问",但这有副作用,我试图避免这种情况.
我可以想到一种在函数式语言中实现它的方法,但它基本上需要将大量的状态传递给不同的函数,我想知道是否有更节省空间的解决方案.
我正在利用Scala在业余时间学习函数式编程,我有一个闲置的新手问题.
在做像Haar小波变换这样的事情时,我可以看到具有不可变对象的优雅 - 即当数据本身由对象表示时不会改变.
但我看到一个博客,其中有人以小游戏为例证明了不变性.如果一个生物对象收到了伤害,它没有改变它的状态 - 它返回了一个新的生物对象,其中包含新的生命值和一个新的"aggro to X"标志.但是,如果我们设计像MMORPG这样的东西,魔兽世界说.战场上的一百名玩家......可能有成千上万的攻击和缓冲/减益效果以不同的方式影响他们.是否仍然可以使用完全不可变的对象来设计系统？对我来说,似乎每个'滴答'会有一大群新的实例.为了获得当前有效的对象实例,所有客户端都会不断地经历某种中心"游戏世界"对象,或者？
函数式编程是否适用于此,或者这是"最佳工作的最佳工具,可能在这里不可变"的情况？
这个问题的背景是我想要使用基因表达式编程(GEP),这是一种使用Erlang的进化算法.GEP使用基于字符串的DSL称为" Karva表示法 ".Karva表示法很容易翻译成表达式解析树,但是翻译算法假定一个实现具有可变对象:在翻译过程的早期创建不完整的子表达式,并且他们自己的子表达式随后用值填充.在他们被创建时不知道.
Karva表示法的目的是保证在没有任何昂贵的编码技术或遗传密码校正的情况下创建语法正确的表达式.问题是,使用像Erlang这样的单任务编程语言,我必须在每个子表达式被填充时不断重新创建表达式树.这需要一个便宜的 - O(n)？ - 更新操作并将其转换为在指数时间内完成的操作(除非我弄错了).如果我找不到将K表达式转换为表达式树的有效函数算法,那么GEP的一个引人注目的特性就会丢失.
我很欣赏K表达式翻译问题非常模糊,所以我想要的是如何将一个固有的非功能性算法(利用可变数据结构的算法)转换为不具备这种算法的算法.纯函数式编程语言如何适应计算机科学早期生成的许多算法和数据结构,这些算法和数据结构依赖于可变性来获得所需的性能特征？
algorithm computer-science functional-programming mutable evolutionary-algorithm