1. 首頁
  2. 問答
  3. 如何在函數式編程語言中實現圖和圖算法？

如何在函數式編程語言中實現圖和圖算法？

2010-06-08 37 views
38

基本上，我知道如何創建圖形數據結構，並在允許使用副作用的編程語言中使用Dijkstra算法。通常，圖形算法使用一種結構來標記某些節點爲「已訪問」，但這有副作用，我試圖避免。如何在函數式編程語言中實現圖和圖算法？

我可以想出一種在函數式語言中實現它的方法，但它基本上需要將大量狀態傳遞給不同的函數，而且我想知道是否有更節省空間的解決方案。

來源

2010-06-08 brad

回答

15

你可以看看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

+7

我把從功能圖形庫頁以下鏈接： 這說明理論： 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

0

我很想聽到一些非常聰明的技術，但我認爲有兩種基本方法：

  1. 修改一些全局狀態對象。即副作用
  2. 將圖形作爲參數傳遞給函數，返回值是修改的圖形。我認爲這是你的「傳遞大量狀態」的方法

這就是在函數式編程中所做的。如果編譯器/解釋器不錯，它將幫助您管理內存。尤其是，如果您碰巧在任何函數中進行遞歸，您都需要確保使用尾遞歸。

來源

2010-06-08 16:16:55 Greg

3

如果您使用的是我熟悉的唯一函數式語言haskell，我會推薦使用State monad。狀態monad是一個函數的抽象，它接受一個狀態並返回一箇中間值和一個新的狀態值。這是considered idiomatic haskell那些需要保持較大狀態的情況。

這是一個更天然的「返回狀態作爲函數結果並將其作爲參數傳遞」的一個更好的替代方案，它在初學者函數式編程教程中強調。我想大多數函數式編程語言都有類似的結構。

來源

2010-06-08 16:28:11 fmark

+0

難道是公平的描述的狀態單子的一塊建立一個單一的功能塊，然後將完成的功能狀態？ – Greg 2010-06-08 17:33:09

+0

@Greg：是的。 Monadizing一些編程習慣用法（在這種情況下，讀/寫全局狀態）是將這種習慣用法轉化爲可組合的一種方式。你將這些碎片綁在一起以獲得更大的碎片。 – dubiousjim 2011-03-21 02:19:06

2

我只是將訪問集合保存爲一個集合並將其作爲參數傳遞。有效的日誌時間實現任何有序類型和超高效的整數集。

要表示一個圖，我使用鄰接列表，或者我將使用一個有限映射將每個節點映射到其後繼列表。這取決於我想要做什麼。

與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

相關問題

 相關問題