时间戳

首页 > 解决方案 > Haskell：使用 List Monad 计算周期

haskell - Haskell：使用 List Monad 计算周期

问题描述

-- 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

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

问题是我不太确定如何使用 list 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没有再次调用，我什至不认为它是递归的......我该如何解决这个问题？

图形

标签： haskellfunctional-programmingmonadsdo-notation

解决方案

在 list monad 中的一行：

x <- f y

期望f返回一个列表。x将依次使用列表的每个值进行实例化，因此该do子句的其余部分将使用这些值中的每一个运行。

您将看到它adjacentNodes返回一个节点列表。因此，从您开始，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）神奇地找到所有可能的路径。这不是完整的答案，但它应该给你足够的开始。

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

推荐阅读