haskell / haskell/containers

Feature request: `traverseKeys` and `traverseKeysWith`

Open
#771 6 comments 0 reactions 0 assignees View on GitHub
feature-request IntMap Map
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

Currently there are functions
```haskell
mapKeys :: (Ord k) => (j -> k) -> Map j a -> Map k a
traverse :: (Applicative f) => (a -> f b) -> Map k a -> f (Map k b)
```
but nothing of the type `(Applicative f, Ord k) => (j -> f k) -> Map j a -> f (Map k a)`.

A sample implementation:
```haskell
traverseKeys :: (Applicative f, Ord k) => (j -> f k) -> Map j a -> f (Map k a)
traverseKeys f = fmap fromList . traverse (\(j, a) -> (,a) <$> f j) . assocs

traverseKeysWith :: (Applicative f, Ord k) => (a -> a -> a) -> (j -> f k) -> Map j a -> f (Map k a)
traverseKeysWith c f = fmap (fromListWith c) . traverse (\(j, a) -> (,a) <$> f j) . assocs
```

which is `O(n log n)`, if I'm not mistaken; though I haven't looked through the internals of the implementation to dig for further optimizations.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.