I just started using Haskell some weeks ago and I lack of imagination to resolve a function in this situation.

So I am trying to find the predecessors of a vertex in a graph implemented in Haskell.

My graph :

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

The function `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
```

And the function I'm currently trying to resolve :

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

I need to find a way to get the keys (the vertices) by having the value (the successor) of those vertices. for example :

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

But when i run that line, i get Non-exhaustive patterns in lambda. What is that and how can i fix it? Thankyou!

Haskell's Maps and Hashmap don't have efficient key lookups. The best you can do is O(n), and you have to write it yourself. I have something like this in my projects, which we can edit a bit to find all keys:

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

You might want to use strict folds if you use strict maps.

October 07, 2019 04:36 AM

- Serverfault Help
- Superuser Help
- Ubuntu Help
- Webapps Help
- Webmasters Help
- Programmers Help
- Dba Help
- Drupal Help
- Wordpress Help
- Magento Help
- Joomla Help
- Android Help
- Apple Help
- Game Help
- Gaming Help
- Blender Help
- Ux Help
- Cooking Help
- Photo Help
- Stats Help
- Math Help
- Diy Help
- Gis Help
- Tex Help
- Meta Help
- Electronics Help
- Stackoverflow Help
- Bitcoin Help
- Ethereum Help