Feature request: Set.traverse

[robrix]

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:

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:

traverse f  = foldMap (fmap singleton . f)

which requires an extra Monoid (f a) constraint, but the latter was resolved by Liam Goodacre:

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?

[treeowl]

I seem to remember some discussion of this already.

…

On Tue, Jun 8, 2021, 12:24 PM Rob Rix ***@***.***> wrote: 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: 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 <https://github.com/chris-martin> came up with this variant <https://twitter.com/chris__martin/status/1401242486702428164>: 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>: 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? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#779>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOOF7LRFDCEABWIIXSYHZDTRY72PANCNFSM46KJPWDQ> .

[sjakobi]

I seem to remember some discussion of this already.

Indeed: #18

[sjakobi]

I've had a need for this function before, so I'm +1 for adding it.

The fromList-based implementation seems reasonable – the Monoid/union-based one looks slower.

[chris-martin]

Hey, I was just considering suggesting this myself.

I'm thinking about where this might fit into the Data.Set API. Maybe it would make sense to relate it to the other things in the "maps" section. It presently looks like this:

map :: Ord b => (a -> b) -> Set a -> Set b
mapMonotonic :: (a -> b) -> Set a -> Set b 

If we were to amend this with an applicative variant, would there be any interest in a monotonic version as well?

map :: Ord b => (a -> b) -> Set a -> Set b
mapMonotonic :: (a -> b) -> Set a -> Set b 
traverse :: (Ord b, Applicative f) => (a -> f b) -> Set a -> f (Set b)
traverseMonotonic :: Applicative f => (a -> f b) -> Set a -> f (Set b)

[chris-martin]

Another possible definition?

traverse f = Set.foldl (\fbs a -> Set.insert <$> f a <*> fbs) (pure Set.empty)

[googleson78]

Any objections to adding this? If there are performance concerns we could highlight this very heavily in the docs, but I think it's convenient to at least have the option to pay "the performance cost".

[treeowl]

I like traverseMonotonic and the

traverse :: (Applicative f, Ord b) => (a -> f b) -> Set a -> f (Set b)
traverse f = getAp . foldMap (Ap . fmap singleton . f)

implementation is certainly very pretty. I'm curious whether it will give some "magical" internal sharing for, say, the [] applicative.

Do we also want a strictly accumulating version something like this?

mapM :: (Monad f, Ord b) => (a -> f b) -> Set a -> f (Set b)
mapM f xs = foldr (\x r !acc -> f x >>= \y -> r (insert y acc)) (pure $!) (toList xs) empty

[treeowl]

Say we have q = Bin n x l r and we write traverse (\a -> [a, a+10]) q. Then the mapping part of foldMap (conceptually) gives Bin n (Ap [singleton x, singleton (x + 10)]) mapped_l mapped_r. The folding part then gives Ap $ liftA2 union folded_l (liftA2 union [singleton x, singleton (x + 10)] folded_r). I guess there's some sharing of union work? Not very magical, but whatever...

[googleson78]

I return a year later, wanting this yet again 😅

[treeowl]

Okay, fine. I won't stand in the way.

[googleson78]

Ah, sorry, I did not mean to say "please stop blocking this", but rather wanted to simply reinforce my interest in having such a function available.