0

几周前我刚开始使用 Haskell，我缺乏想象力来解决这种情况下的功能。

所以我试图在用 Haskell 实现的图中找到一个顶点的前身。

我的图表：

-- | A directed graph
data Graph v = Graph
    { arcsMap :: Map v [v]     -- A map associating a vertex with its successors
    , labelMap :: Map v String -- The Graphviz label of each node
    , styleMap :: Map v String -- The Graphviz style of each node
    }

功能successors：

-- | Returns the successors of a vertex in a graph in ascending order
--
-- We say that `v` is a successor of `u` in a graph `G` if the arc `(u,v)`
-- belongs to `G`.
-- Note: Returns the empty list if the vertex does not belong to the graph.
successors :: Ord v => v -> Graph v -> [v]
successors v (Graph arcs _ _) = findWithDefault [] v arcs

我目前正在尝试解决的功能：

-- | Returns the predecessors of a vertex in a graph in ascending order
--
-- We say that `u` is a predecessor of `v` in a graph `G` if the arc `(u,v)`
-- belongs to `G`.
-- Note: Returns the empty list if the vertex does not belong to the graph.
predecessors :: Ord v => v -> Graph v -> [v]
predecessors v  (Graph arcs _ _) = 
     map (fst)  (filter (\(x,[y]) -> elem v [y]) (assocs arcs) )

我需要找到一种通过获取这些顶点的值（后继）来获取键（顶点）的方法。例如 ：

-- >>> predecessors 3 $ addArcs emptyGraph [(1,2),(2,3),(1,3)]
-- [1,2]

但是当我运行那条线时，我 在 lambda 中得到了非详尽的模式。

那是什么，我该如何解决？谢谢！

  • 编辑：没关系，我纠正了它，但我还是不太明白哈哈
4

1 回答 1

2

Haskell 的 Maps 和 Hashmap 没有有效的键查找。你能做的最好是 O(n)，你必须自己写。我的项目中有类似的东西，我们可以对其进行一些编辑以找到所有键：

lookupKey :: Eq v => v -> Map.Map k v -> [k]
lookupKey val = Map.foldrWithKey go [] where
  go key value found =
    if value == val
    then key:found
    else found

如果您使用严格的地图，您可能想要使用严格的折叠。

于 2019-10-07T04:36:08.670 回答