如何在函数式编程语言中实现图和图算法？

基本上，我知道如何创建图形数据结构，并在允许使用副作用的编程语言中使用Dijkstra算法。通常，图形算法使用一种结构来标记某些节点为“已访问”，但这有副作用，我试图避免。如何在函数式编程语言中实现图和图算法？

我可以想出一种在函数式语言中实现它的方法，但它基本上需要将大量状态传递给不同的函数，而且我想知道是否有更节省空间的解决方案。

2010-06-08 brad

你可以看看Martin Erwig的Haskell functional graph library是如何做的。例如，它的shortest-path functions都是纯粹的，你可以看到source code它是如何实现的。

另一个选项like fmark mentioned是使用一种抽象，它允许您根据状态实现纯函数。他提到了国家monad（可在lazy和strict品种中获得）。另一种选择是，如果您在GHC Haskell编译器/解释器（或者我认为支持rank-2类型的任何Haskell实现）中工作，另一种选择是the ST monad，它允许您编写纯函数来处理内部的可变变量。

来源

2010-06-08 17:30:16

我把从功能图形库页以下链接：这说明理论： http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01 此文档的编程细节： http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl0103.pdf 在一起，这些论文最好回答我的问题，特别是第二个问题，这是更实际一点。谢谢！ – brad 2010-06-08 18:13:24

-1

大多数函数式语言都支持内部函数。所以你可以在最外层创建你的图形表示，并从内部函数中引用它。

这本书涵盖广泛它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

来源

2010-06-08 16:09:32 Vlad

我很想听到一些非常聪明的技术，但我认为有两种基本方法：

修改一些全局状态对象。即副作用
将图形作为参数传递给函数，返回值是修改的图形。我认为这是你的“传递大量状态”的方法

这就是在函数式编程中所做的。如果编译器/解释器不错，它将帮助您管理内存。尤其是，如果您碰巧在任何函数中进行递归，您都需要确保使用尾递归。

来源

2010-06-08 16:16:55 Greg

如果您使用的是我熟悉的唯一函数式语言haskell，我会推荐使用State monad。状态monad是一个函数的抽象，它接受一个状态并返回一个中间值和一个新的状态值。这是considered idiomatic haskell那些需要保持较大状态的情况。

这是一个更天然的“返回状态作为函数结果并将其作为参数传递”的一个更好的替代方案，它在初学者函数式编程教程中强调。我想大多数函数式编程语言都有类似的结构。

来源

2010-06-08 16:28:11 fmark

难道是公平的描述的状态单子的一块建立一个单一的功能块，然后将完成的功能状态？ – Greg 2010-06-08 17:33:09

@Greg：是的。 Monadizing一些编程习惯用法（在这种情况下，读/写全局状态）是将这种习惯用法转化为可组合的一种方式。你将这些碎片绑在一起以获得更大的碎片。 – dubiousjim 2011-03-21 02:19:06

我只是将访问集合保存为一个集合并将其作为参数传递。有效的日志时间实现任何有序类型和超高效的整数集。

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

与Abelson和Sussman相比，我推荐Chris Okasaki的Purely Functional Data Structures。我已经联系了克里斯的论文，但如果你有这笔钱，他将它扩大到excellent book。

只是为了咧嘴笑，这里有一个稍微可怕的反向后序深度优先搜索在Haskell中的延续传递风格中完成。这是直接出Hoopl优化器库：

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e) 
          => LabelMap (block C C) -> e -> LabelSet -> [block C C] 
postorder_dfs_from_except blocks b visited = 
vchildren (get_children b) (\acc _visited -> acc) [] visited 
where 
    vnode :: block C C -> ([block C C] -> LabelSet -> a) 
         -> ([block C C] -> 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

来源

2010-06-08 22:58:32

这是一个Swift示例。你可能会发现这更具可读性。变量实际上是描述性命名的，与超级神秘的Haskell示例不同。

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

来源

2017-07-29 11:14:48 CommaToast

如何在函数式编程语言中实现图和图算法？

回答

相关问题