如何在函数式编程语言中实现graphics和graphicsalgorithm?

基本上,我知道如何创buildgraphics数据结构,并在允许副作用的编程语言中使用Dijkstraalgorithm。 通常情况下,图algorithm使用一个结构来标记某些节点为“访问”,但这有副作用,我试图避免。

我可以想到一种用函数式语言来实现这一点的方法,但是它基本上需要将大量的状态传递给不同的函数,而且我想知道是否有更加节省空间的解决scheme。

您可以查看Martin Erwig的Haskell function图库如何操作。 例如,它的最短path函数都是纯粹的,你可以看到源代码是如何实现的。

另一个选项, 如fmark提到的 ,是使用一个抽象,允许你在状态方面实现纯粹的function。 他提到国家monad(这是懒惰和严格的品种)。 另一个select是,如果你在GHC Haskell编译器/解释器(或者我认为是任何支持rank-2types的Haskell实现)工作,另一个select是ST monad ,它允许你写纯函数来处理mutable内部variables。

如果您使用的是我熟悉的唯一函数式语言haskell,我会推荐使用State monad 。 状态monad是一个抽象函数,它接受一个状态并返回一个中间值和一个新的状态值。 对于那些需要维护一个大型状态的情况,这被认为是习惯性的haskell

对于天真的“返回状态作为函数结果并将其作为parameter passing”,这在初学函数式编程教程中强调的是一个更好的select。 我想大多数函数式编程语言都有类似的结构。

我只是将访问集合保存为一个集合,并将其作为parameter passing。 有效的日志时间实现任何有序types和超高效的整数集。

为了表示一个图,我使用邻接表,或者我将使用一个有限映射将每个节点映射到其后继列表。 这取决于我想要做什么。

我推荐Chris Okasaki的纯粹function数据结构 ,而不是Abelson和Sussman。 我把克里斯的论文联系在一起,但是如果你有钱的话,他把它扩展成一本很好的书 。


只是为了咧嘴笑,这里有一个稍微可怕的反向后序深度优先search在Haskell中以连续传递的方式完成。 这是从Hoopl优化器库直接出来的:

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e) => LabelMap (block CC) -> e -> LabelSet -> [block CC] postorder_dfs_from_except blocks b visited = vchildren (get_children b) (\acc _visited -> acc) [] visited where vnode :: block CC -> ([block CC] -> LabelSet -> a) -> ([block CC] -> LabelSet -> a) vnode block cont acc visited = if setMember id visited then cont acc visited else let cont' acc visited = cont (block:acc) visited in vchildren (get_children block) cont' acc (setInsert id visited) where id = entryLabel block vchildren bs cont acc visited = next bs acc visited where next children acc visited = case children of [] -> cont acc visited (b:bs) -> vnode b (next bs) acc visited get_children block = foldr add_id [] $ targetLabels bloc add_id id rst = case lookupFact id blocks of Just b -> b : rst Nothing -> rst 

我很想听听一些非常聪明的技巧,但我认为有两个基本的方法:

  1. 修改一些全局状态对象。 即副作用
  2. 将graphics作为parameter passing给函数,返回值是修改后的graphics。 我认为这是你“传递大量状态”的方法

这就是函数式编程所做的。 如果编译器/解释器是好的,它将帮助你pipe理内存。 尤其是,如果碰巧在你的任何函数中recursion,你都要确保使用尾recursion。

这是一个Swift示例。 你可能会发现这更可读。 variables实际上是描述性命名的,不像超级神秘的Haskell例子。

https://github.com/gistya/Functional-Swift-Graph

大多数function语言都支持内部函数 所以你可以在最外层创build你的graphics表示,只需从内部函数中引用它。

本书广泛涵盖了http://www.amazon.com/gp/product/0262510871/ref=pd_lpo_k2_dp_sr_1?ie=UTF8&cloe_id=aa7c71b1-f0f7-4fca-8003-525e801b8d46&attrMsgId=LPWidget-A1&pf_rd_p=486539851&pf_rd_s=lpo-top-stripe -1&pf_rd_t = 201&pf_rd_i = 0262011530&pf_rd_m = ATVPDKIKX0DER&pf_rd_r = 114DJE8K5BG75B86E1QS