Haskell：使用 List Monad 计算周期

Question

-- 1. Graph structure: nodes and adjacency matrix (i.e. the edges) 
data Node = A | B | C | D | E | F deriving (Show,Eq,Ord)

adj :: (Node,Node) -> Bool
adj p = case p of
  (A,B) -> True
  (A,C) -> True  
  (B,C) -> True
  (B,F) -> True
  (C,D) -> True
  (D,E) -> True
  (E,B) -> True
  (E,F) -> True
  (F,A) -> True
  (_,_) -> False

type Path = [Node]

-- 2. Auxiliary functions
adjacentNodes :: Node -> [Node] -> [Node]
adjacentNodes n ns = filter (\x -> adj(n,x)) ns

allNodes :: [Node]
allNodes = [A,B,C,D,E,F]

choice :: ([a],[a]) -> [a]
choice = uncurry (++)

-- 3. To do
addtoEnd :: Path -> [Node] -> [Path]
addtoEnd p ns = undefined

hCycles :: Node -> [Path]
hCycles n = undefined

我有这段代码（它是给我们的，我无法更改它或类型）并且需要使用列表 monad（和 do 表示法）定义函数 hCycles。 hCycles 应该计算图像中图的任何通用节点的哈密顿循环。

问题是我不太确定如何使用列表 monad 来做到这一点...尽管如此，我认为我有该函数的第一个版本：

hCycles :: Node -> [Path]
hCycles n = do 
            p <- [[n]]
            nextNode <- adjacentNodes n allNodes
            if n == nextNode
            then [p]
            else addtoEnd p allNodes

if/else 案例仍然有一个奇怪的行为，并且由于 hCycles 没有被再次调用，我什至不认为它是递归的......我该如何解决这个问题？

Answer 1

在列表 monad 中有一行格式：

x <- f y

需要 f 到 return 一个列表。 x 将依次使用列表的每个值进行实例化，因此 do 子句的其余部分将运行与每个值一起实例化。

您将看到 adjacentNodes return 是一个节点列表。所以从 n 开始，你可以像这样考虑它连接的每个节点：

nextNode <- adjacentNode n allNodes

写这个函数：

steps :: [Nodes] -> Path -> [Path]
steps _ [] = fail "Need a node to start with."
steps ns path@(n:rest) = do
   nextNode <- adjacentNode n ns
   guard $ not $ elem nextNode path   -- Stop if we've already visited this node.
   return $ nextNode : path

你可以把它想象成寻找单一路径的算法，它（多亏了 list monad）神奇地找到了所有可能的路径。这不是全部答案，但应该足以让您入门。

（注意：我还没有实际测试过这段代码。）

Answer 2

您好，我想有足够的时间给您一些可以解决您问题的版本：

hCycles :: Node -> [Path]
hCycles n = 
    filter isValidPathLength $ map (n:) $ go [] (adjacentNodes n allNodes)
    where
    isValidPathLength path =
        length path == length allNodes + 1
    -- note: go will only care about a path to n 
    -- but will take care of not visiting nodes two-times
    go _ [] = [] -- fail if there is no node left to discover
    go visited toVisit = do
        cur <- toVisit
        if cur == n then
            pure [n] -- found n
        else do
            let neighboursToVisit = filter (`notElem` visited) $ adjacentNodes cur allNodes
            pathToEnd <- go (cur:visited) neighboursToVisit
            pure $ cur:pathToEnd

我发现你的adj不适合你的照片所以我把它改成了

adj :: (Node,Node) -> Bool
adj p = case p of
  (A,B) -> True
  (A,C) -> True  
  (B,C) -> True
  (B,F) -> True
  (C,D) -> True
  (D,E) -> True
  (E,B) -> True
  (E,F) -> True
  (F,A) -> True
  (_,_) -> False

（你的好像不是有向图）

有了这个你会得到：

> hCycles A
[[A,B,C,D,E,F,A],[A,C,D,E,B,F,A]]

一些笔记:

我不关心这里的性能（例如，有更好的数据结构来管理 visited 然后是列表） - 这个进行强力深度优先搜索 - 如果你想要你可以使它适应 BFS - 这是 IMO 的一个很好的练习（你可能想要摆脱 do 符号的东西......嘿你要求它）

Haskell：使用 List Monad 计算周期

Haskell: Compute Cycles with List Monad

haskell

functional-programming

monads

do-notation