CODEWITHSUNDEEP
haskell
Fiona Runge
Fiona Runge

Reputation: 2311

mapM for Data.Set in Haskell

So I have some Haskell code in which I'd like to work with Data.Set. Basically because I didn't look into alternatives much and need a structure to store elements of Ord without duplicates.

I've now come to a situation where I'd like to have something like mapM for Data.Set so that I can perform monadic operations on a sets individual elements. I already searched Hayoo for a type like (a -> m b) -> Set a -> m (Set b) but didn't find anything useful.

I also looked into Data.Traversable just to find out that it has instances for [], Maybe and (Map k) but not for Set.

So my questions are:

  1. Why is there no mapM for Set in Data.Set?
  2. Is there already a package that delivers something like mapM that I missed?
  3. Is it discouraged to want to mapM over Sets? (why and what are alternatives?)

Upvotes: 1

Views: 1144

Answers (2)

Petr
Petr

Reputation: 63359

You might be interested in the lens package. It provides a more general abstraction for traversals (among many other things). While it doesn't solve the problem of having an efficient mapM for Sets, it allows to express traversals for constrained data types:

import Control.Lens.Traversal
import Data.Traversable (traverse)
import Data.Set (Set)
import qualified Data.Set as Set

-- forall f. Applicative f => (a -> f b) -> Set a -> f (Set b)
setTraversal :: (Ord b) => Traversal (Set a) (Set b) a b
setTraversal f = (fmap Set.fromList) . traverse f . Set.toList

main = do
    print $ mapMOf setTraversal (\x -> [x+1, x-1]) $ Set.fromList [0, 10, 20]

Note that the documentation for Set.toList says that it's subject to list fusion. With some luck (depending on the applicative in question) the intermediate lists could get fused away.

Upvotes: 4

hammar
hammar

Reputation: 139860

The main problem is that Traversable requires Functor, and sets cannot be functors since they require an Ord constraint while functors must be unconstrained.

However, sets are foldable so if you don't need to collect the results, you can use mapM_ from Data.Foldable.

If you do need the results, you can go via lists, e.g.

fromList <$> mapM f (toList s)

Upvotes: 8

Related Questions