Haskell: catMaybe for Data.Set?

Question

how would you implement a catMaybes for Data.Set ?

I came up with:

import qualified Data.Set as Set
import qualified Data.Maybe as Maybe
setCatMaybes a = Set.map Maybe.fromJust . Set.delete Nothing $ a

fnord = Set.fromList [Nothing, Just 41, Just 43, Just 47]

then i get the following

setCatMaybes fnord == fromList [41,43,47]

Answer 1

I think the solution you already have is probably the best one. Along the lines of John's solution, here's a fairly short one:

setCatMaybes :: Ord a => Set.Set (Maybe a) -> Set.Set a
setCatMaybes s = Set.fromAscList [x | Just x <- Set.toAscList s]

Or here's a longer one, that may be faster:

setCatMaybes2 :: Ord a => Set.Set (Maybe a) -> Set.Set a
setCatMaybes2 s
  | Set.null s = Set.empty
  | otherwise  = Set.mapMonotonic Maybe.fromJust $ case Set.deleteFindMin s of
                   (Nothing, s') ->  s'
                   _ -> s

Answer 2

Since Set (Maybe a) is such a weird type, which appears only after the application of f :: a -> Maybe b, why not kill two birds with one stone and create a mapMaybe for Data.Set?

import qualified Data.Set
import qualified Data.Maybe

mapMaybe :: Ord b => (a -> Maybe b) -> Data.Set.Set a -> Data.Set.Set b
mapMaybe f = Data.Set.fromList . Data.Maybe.mapMaybe f . Data.Set.toList

In this way, the weird Set (Maybe a) never exists.

Answer 3

How about just this:

setCatMaybes = Set.fromList . catMaybes

This will only require traversing the list once, as Set.fromList is a good consumer.