我正在嘗試向 Haskell 中的圖形添加一條邊，其中圖形資料型別定義為：
data Graph a = Graph [(a, [a])]
deriving (Show)
實際上，我的資料型別定義為： Graph 是存盤為元組的節點串列，其中第一個元素是節點值，第二個元素是其邊的串列（即，它連接到哪些其他節點）。
在兩個節點 (u,v) 之間插入邊時，您首先必須檢查兩個節點是否存在并且邊不存在。也就是說， (u, [a,b...n]) 和 (v,[a,b...n]) 它們各自的邊串列不包含 u 或 v。因此，我有兩個函式執行此檢查。如果此檢查通過并且由于我的資料型別如上所述定義，我必須在相應節點的串列中插入 u 和 v。在此之后，我必須回傳一個新的 Graph。
addEdge :: Eq a => Graph a -> (a, a) -> Graph a
addEdge g (u, v)
| (existsNode u g) && (existsNode v g) && (not (existsEdge (u, v) g)) = undefined
| otherwise = g
-- Check if an edge between two nodes exists
existsEdge :: Eq a => (a, a) -> Graph a -> Bool
existsEdge (u, v) g = elem u (getEdges (u, v) g) && elem v (getEdges (u, v) g)
getEdges :: Eq a => (a, a) -> Graph a -> [a]
getEdges (u, v) g =
let rightNeighbours = getNodeNeighbours (getNode u g)
leftNeihbours = getNodeNeighbours (getNode v g)
in rightNeighbours leftNeihbours
-- Get a node given its node id
getNode :: Eq a => a -> Graph a -> (a, [a])
getNode y (Graph []) = (y, [])
getNode y (Graph (x : xs))
| y == fst x = x
| otherwise = getNode y (Graph xs)
我需要一種方法來填充現在未定義的部分，其中包含每個節點 u 和 v，并將 v 附加到 u 的鄰居串列（u，[v]），反之亦然（v，[u]），這導致回傳一個圖表。
例如，如果我們有：
g = (Graph [(1,[2]),(2,[1]), (3,[2])])
我們想在節點 3 和 1 之間添加一條邊。我們首先看到兩個節點都存在，并且邊不存在 -->
g = (Graph [(1,[2,3]),(2,[1]), (3,[2,1])])
有沒有辦法在 Haskell 中做到這一點？
uj5u.com熱心網友回復：
這是一個通用經驗法則的好例子：
避免布爾檢查，然后有條件地做某事。而是撰寫嘗試做某事的函式，如果不可能，則失敗。
你的任務可以分解為：
- 挑選出您想要邊緣的兩個節點（如果它們存在）。您應該以一種允許調整它們的方式來執行此操作，而不僅僅是讀出。
- 修改其中一個節點的邊串列，插入新邊（如果不存在）。
失敗案例應該與一個Maybe型別相關聯：如果一個操作是不可能的，讓它靜默失敗通常是一個壞主意，相反，你應該明確表示沒有應用更新，然后把它留給呼叫者忽略它或做其他事情。
addEdge :: Eq a => Graph a -> (a, a) -> Maybe (Graph a)
現在，我所說的“以允許調整 [節點] 的方式執行此操作”是什么意思？這意味著您應該回傳一個舊版本的視圖，以及一個函式，給定節點的修改值，重建整個圖形的相應修改版本。具體來說，您要修改傳出邊。（修改節點的密鑰還需要更新可能指向它的所有其他節點；我們不需要。）
getNode :: Eq a => a -> Graph a -> Maybe ((a, [a]), [a] -> Graph a)
這個簽名看起來有點嚇人；讓我們介紹一些型別同義詞以使其更容易：
type Node a = (a, [a])
type NodeView a = (Node a, [a] -> Graph a)
getNode :: Eq a => a -> Graph a -> Maybe (NodeView a)
實作的主要變化是您需要“記住”串列中因為不匹配而被跳過的節點。我會用一個輔助功能來做到這一點
getNode' :: Eq a => a -> Graph a
-> [Node a] -- ^ The nodes that need to be prepended in the reconstructed graph
-> Maybe (NodeView a)
getNode' _ _ (Graph []) = Nothing -- Node was not found
getNode' y prep (Graph ((x,es):ns))
| x==y -- Node was found, now create a view to it:
= Just ( (x,es)
, \es' -> Graph $ prep (x,es') : xs )
| otherwise -- Not found yet, but maybe later. Add currently tried node to the prep-list.
= getNode' y ((x,es):prep) (Graph ns)
Obs：以上內容對重建圖進行了更改，這對您來說可能很重要，也可能無關緊要。你能看出它是什么嗎？
在實踐中，您不應該getNode'直接使用，而是始終使用空prep串列呼叫它。事實上，您可能應該將其設為本地“回圈體”函式：
getNode :: Eq a => a -> Graph a -> Maybe (NodeView a)
getNode y = go y []
where go _ _ (Graph []) = Nothing
go y prep (Graph ((x,es):ns)) = ...
對于任務的其余部分，您可以使用NodeView此函式給出的作為幫助器來創建整個更新的圖形。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/517148.html
標籤：哈斯克尔