haskell - 返回由 Haskell 中的两次插入修改的图

Question

我正在尝试向 Haskell 中的图形添加一条边，其中图形数据类型定义为:

data Graph a = Graph [(a, [a])]
  deriving (Show)

实际上，我的数据类型定义为:图是存储为元组的节点列表，其中第一个元素是节点值，第二个元素是其边的列表(即它连接的其他节点到)。

在两个节点 (u,v) 之间插入一条边时，首先必须检查两个节点是否都存在，以及这条边是否已经存在。也就是说，(u, [a,b...n]) 和 (v,[a,b...n]) 它们各自的边列表不包含 u 或 v。因此，我有两个函数执行此检查。如果此检查通过并且由于我的数据类型定义如上，我必须在相应节点的列表中插入 u 和 v。在此之后，我必须返回一个新的图表。

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 中做到这一点？

Answer 1

这是通用经验法则的一个很好的例子:

避免 bool 检查然后有条件地做某事。而是编写尝试做某事的函数，如果做不到就失败。

您的任务可以分解为:

• 选出您想要在其间设置边(如果存在)的两个节点。你应该以一种允许调整它们的方式来做到这一点，而不仅仅是读出。
• 修改其中一个节点的边列表，插入新边(如果不存在)。

失败案例应该与Maybe 类型相关联:如果一个操作是不可能的，让它默默地失败通常是一个坏主意，相反你应该明确更新是' 应用，然后将其留给调用者忽略它或做其他事情。

addEdge :: Eq a => Graph a -> (a, a) -> Maybe (Graph a)

现在，我所说的“以允许调整 [节点] 的方式执行此操作”是什么意思？这意味着您应该返回一个旧版本的 View ，以及一个函数，该函数在给定节点的修改值的情况下重建整个图的相应修改版本。具体来说，您要修改传出边。 (修改节点的 key 还需要更新可能指向它的所有其他节点；我们不需要那个。)

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 作为帮助程序来创建整个更新图。