Найти ключ по его значению с помощью Data.Map в Haskell

Question

Я только начал использовать 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]

Но когда я запускаю эту строку, я получаю Неисчерпывающие паттерны в лямбде .

Что это такое и как я могу это исправить? Спасибо!

• Редактировать: Неважно, я исправил это, но я до сих пор не понимаю, как хаха

Answer 1

Карты и Hashmap на Haskell не имеют эффективных поисков по ключевым словам. Лучшее, что вы можете сделать, это 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 val:found
    else found

Вы можете использовать строгие сгибы, если используете строгие карты.