haskell / haskell/containers

Feature request: Set.traverse

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

Description

We can’t have a `Traversable` instance for `Set`, but there’s no reason we can’t have a constrained `traverse` just like we have `Set.map` even tho we can’t have `Functor` either. My initial attempt uses `toList`/`fromList`:

```haskell
traverse :: (Ord b, Applicative f) => (a -> f b) -> Set a -> f (Set b)
traverse f = fmap fromList . Prelude.traverse f . toList
```

When I asked around on Twitter, @chris-martin [came up with this variant](https://twitter.com/chris__martin/status/1401242486702428164):

```haskell
traverse f = foldMap (fmap singleton . f)
```

which requires an extra `Monoid (f a)` constraint, but the latter was [resolved by Liam Goodacre](https://twitter.com/goodacre_liam/status/1401430713820487681):

```haskell
traverse f = getAp . foldMap (Ap . singleton . f)
```

I haven’t thought too hard about the asymptotics or other performance characteristics here, and there may well be better implementations possible, but it was certainly a fun thought experiment! What do folks think about adding a `traverse` for `Set`?

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.