Haskell:使用Data.Map.elems的函数

Question

嗨,我试图从中返回一个值,Data.Map.Map 但无法得到正确的值,这里是相关的代码:

data Graph v = Graph (Map.Map v [v])

edges :: Ord v => Graph v -> [(v,v)]
edges (Graph v) = Map.elems v

但是,这不起作用,预期值的示例: [(1,2),(1,3),(3,4)]

我收到错误:

Expected type: Map.Map v (v, v) Actual type: Map.Map v [v]

Answer 1

elems :: Map k a -> [a]只会给你地图的价值,你可能对此更感兴趣assocs :: Map k a -> [(k,a)].

但是如果我们使用它,我们仍然无法获得所需的结果,因为这将构造一个我们得到的元组列表[(v, [v])],因此我们需要将每个2元组(x, [y1, y2, ..., yn])转换为n元组[(x, yi)].为实现这一目标,我们可以使用列表理解:

edges :: Graph v -> [(v,v)]
edges (Graph v) = [ (x, y) | (x, ys) <- Map.assocs v, y <- ys]

如果我们想要排序边缘列表(首先是元组的第一项,然后是第二项),我们可以使用sort :: Ord a => [a] -> [a]:

import Data.List(sort)

edges_sort :: Ord v => Graph v -> [(v,v)]
edges_sort (Graph v) = sort [ (x, y) | (x, ys) <- Map.assocs v, y <- ys]

或者我们可以定义两者:

import Data.List(sort)

edges :: Graph v -> [(v,v)]
edges (Graph v) = [ (x, y) | (x, ys) <- Map.assocs v, y <- ys]

edges_sort :: Ord v => Graph v -> [(v,v)]
edges_sort = sort . edges

一些评论:

就像@amalloy说的那样,我们可以使用list monads而不是list comprehension,并使用sequence :: (Monad m, Traversable t) => t (m a) -> m (t a):

edges :: Graph v -> [(v,v)]
edges (Graph v) = Map.assocs v >>= sequence

就像@luqui说的那样,我们也只能对值列表进行排序,因为规范是键已经排序,所以:

edges :: Graph v -> [(v,v)]
edges (Graph v) = [ (x, y) | (x, ys) <- Map.assocs v, y <- sort ys]