我有一個節點和邊的串列，表示為元組，其中第一個元素是一個節點，第二個元素是它有一個邊的所有節點的串列。我正在嘗試像這樣反轉串列：
ghci> snuN [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
ghci> [("a",["c"]),("b",["a"]),("c",["b"]),("d",["c","e"]),("e",[])]
到目前為止，我已經撰寫了這段代碼：
snuH :: Eq t => [(t,[t])] -> [(t,[t])]
snuH [] = []
snuH ps@((x, xs):rest) =
if (length xs <= 1) && not (x `isInSublist` ps)
then [(y,[x])| y <- xs] snuH rest [(x, [])]
else [(y,[x])| y <- xs] snuH rest
isInSublist :: Eq t => t -> [(t,[t])] -> Bool
isInSublist _ [] = False
isInSublist x ((y, ys):rest) = (x `elem` ys) || isInSublist x rest
combine :: Eq t => [(t,[t])] -> [(t,[t])]
combine ps@((x, xs):(y, ys):rest) = if x == y then (x, xs ys):rest else (x, xs):combine((y, ys):rest)
snuN :: Eq t => [(t, [t])] -> [(t, [t])]
snuN ls = combine $ snuH ls
第一個函式給了我這個輸出：
ghci> snuH [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
ghci> [("b",["a"]),("c",["b"]),("a",["c"]),("d",["c"]),("d",["e"]),("e",[]),("b",[])]
這不是我想要的結果，因為它創建了兩個具有相同第一個元素 ( ("d",["c"]),("d",["e"])) 的元組，并且("b",[])在不應該時它具有額外的元素作為元素。我撰寫了combine幫助函式來解決這個問題，它給了我這個輸出：
ghci> snuN [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
ghci> [("b",["a"]),("c",["b"]),("a",["c"]),("d",["c","e"]),("e",[]),("b",[])]
這解決了具有相同第一個元素的兩個元組的問題，但我仍然有額外的問題("b",[])，我無法弄清楚如何解決，我認為我的有問題，snuH但我看不出問題出在哪里。
Can you tell me what im doing wrong here? I don't understan why I get the extra ("b",[]). All help is appreciated!
uj5u.com熱心網友回復：
我認為以下串列理解為您提供了所需的內容：
type Graph node = [(node, [node])]
converse :: Eq node => Graph node -> Graph node
converse g = [(v, [e | (e, es) <- g, v `elem` es]) | (v, _) <- g]
但是，如果您嘗試一下，您將獲得：
> converse [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
[("a",["c"]),("b",["a"]),("c",["b"]),("e",[])]
與您提供的示例相比，"d"輸出中缺少條目。那是因為輸入沒有提到顯式條目("d", [])。
為了彌補這一點，我們可以在從圖中檢索完整的節點串列時加入更多邏輯，同時考慮“隱含”的節點：
nodes :: Eq node => Graph node -> [node]
nodes g = nub $ concat [v : es | (v, es) <- g]
注意：這需要nub從Data.List.
然后，我們可以寫：
converse' :: Eq node => Graph node -> Graph node
converse' g = [(v, [e | (e, es) <- g, v `elem` es]) | v <- nodes g]
而且，確實，我們產生了：
> converse' [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
[("a",["c"]),("b",["a"]),("c",["b"]),("d",["c","e"]),("e",[])]
uj5u.com熱心網友回復：
你有[(a, [a])]，它將節點映射到它們有邊緣的節點。“反轉”它的一種方法是首先將其轉換為所有邊的串列。我們實際上可以在這里稍微概括一下型別，以區分節點和節點。
allEdges :: [(a, [b])] -> [(a, b)]
allEdges g = [(a, b) | (a, bs) <- g, b <- bs]
現在只需將具有邊緣的節點聚集到每個特定節點即可：
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as M
gather :: Ord b => [(a,b)] -> Map b [a]
gather edges = M.fromListWith ( ) [(b, [a]) | (a, b) <- edges]
現在我們可以使用M.assocs將該地圖轉換為串列！
上面的代碼將留出一些沒有邊緣節點會向他們。我們可以通過一些額外的作業來修補它。
reverseGraph :: Ord a => [(a, [a])] -> [(a, [a])]
reverseGraph = M.assocs . M.fromListWith ( ) . gunk
where
gunk g = [q | (a, bs) <- g, q <- (a, []) : [(b, [a]) | b <- bs]]
這里的想法是，當我們看到 時(a, bs)，我們為每個in插入空邊集(a, [])和非空邊集。(b, [a]bbs
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/359150.html