我想檢查可以從哪些節點訪問節點。
所以我想給出一個圖形和節點，并回傳一個我可以從中訪問圖形的所有節點的串列。（我知道有Data.Graph，但我想嘗試從頭開始理解它，不要故意使用它。
為了建立圖表，我得到了以下資料。
data Node = Node String [Node]
String 只是節點名稱的表示。
這是圖形的表示。
node1 = Node "node1" [node2,node3]
node2 = Node "node2" [node3]
node3 = Node "node3" [node4,node5]
node4 = Node "node4" [node1,node2]
node5 = Node "node5" [node4]
我也得到了（直接）到達節點：
canReachNext (Node x y) = y
現在我的基本想法是這樣的：
listForReachables:: Node n => n -> [n]
listForReachables x
| contains[x] (canReachNext x) == False = listForReachables (head(canReachNext (x)))
| contains [x] (canReachNext x)== True = [x]
| otherwise = []
如果我跑，這將以無限回圈結束
listForReachables node1
我明白它以回圈結束的原因。因為在這個例子中，頭部總是有另一個串列。
我的問題和我卡住的地方是，我習慣了 OOP，在這種情況下，我覺得我需要一個串列來記住我檢查過哪些節點，以及我仍然需要檢查哪些節點。
uj5u.com熱心網友回復：
在 Haskell 中，一個具有所需型別的函式呼叫另一個具有多個引數的函式是很常見的。您可以使用這些來捕獲中間狀態。
在本例中，我添加了已訪問過的節點串列。第一個引數是要探索的節點串列。當程式遇到一個已經通過的節點時，它會丟棄它并從第一個引數開始處理其他節點。
您的退出條件不會發生，因為Bool只有True和False值。這些不再需要比較。
我有一個問題是，標準類Show，并Eq在應用到掛node1，所以我做了一個不完全contains和name自己。
如果您在騎自行車時遇到問題，請務必檢查show node1并解決問題contains。或者，制作一個非回圈測驗圖。
node6 = Node "node6" [node7]
node7 = Node "node7" []
代碼：
data Node = Node String [Node]
node1 = Node "node1" [node2,node3]
node2 = Node "node2" [node3]
node3 = Node "node3" [node4,node5]
node4 = Node "node4" [node1,node2]
node5 = Node "node5" [node4]
canReachNext :: Node -> [Node]
canReachNext (Node x y) = y
name :: Node -> String
name (Node x y) = x
contains :: [Node] -> [Node] -> Bool
contains (x:xs) ys = any ((\(Node a b) -> \(Node c d) -> a == c) x) ys
listForReachables :: Node -> [Node]
listForReachables x = listForReachables' (x:[]) []
listForReachables' :: [Node] -> [Node] -> [Node]
listForReachables' (x:xs) ys
| contains [x] ys = listForReachables' xs ys
| otherwise = listForReachables' (xs canReachNext x) (x:ys)
listForReachables' [] ys = ys
測驗：
map name $ listForReachables node1
輸出：
["node5","node4","node3","node2","node1"]
注 1：有約定將輔助函式命名為 "go"。
listForReachables :: Node -> [Node]
listForReachables x = go (x:[]) [] where
go (x:xs) ys
| contains [x] ys = go xs ys
| otherwise = go (xs canReachNext x) (x:ys)
go [] ys = ys
uj5u.com熱心網友回復：
感覺就像我需要一個串列來記住我檢查過哪些節點，以及我還需要檢查哪些節點。
我同意。所以讓我們使用一個！
listForReachables :: Node -> [String] -> ([String], [Node])
listForReachables node@(Node src tgts) visited
| src `elem` visited = (visited, [])
| otherwise = loopOver tgts (src:visited)
where
loopOver [] visited = (visited, [node])
loopOver (tgt:tgts) visited = let
(visited', reachables) = listForReachables tgt visited'
(visited'', reachables') = loopOver tgts visited'
in (visited'', reachables reachables')
實際上，有經驗的 Haskeller 會注意到這種模式：
(visited', reachables) = listForReachables tgt visited'
(visited'', reachables') = loopOver tgts visited'
并認識到這正是實施(>>=)的State [String]單子。所以他們可能會以這種方式改變實作：
listForReachables :: Node -> State [String] [Node]
listForReachables node@(Node src tgts) = do
done <- gets (src `elem`)
if done then pure [] else do
modify (src:)
reachables <- mapM listForReachables tgts
pure (node : concat reachables)
相當緊湊！讓我們試試看：
> name (Node nm _) = nm
> map name (evalState (listForReachables node1) [])
["node1","node2","node3","node4","node5"]
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/374158.html