Graph of a partial function in Haskell: a -> Maybe b -> [a] -> [(a, b)]

Question

Given a partial function f and a list of arguments xs, I'm looking for the list of pairs (x, f(x)) where f is defined. This seems like a natural thing to do, but so far I've failed to express it elegantly. I wonder if there's anything in the Maybe/Monad/Applicative/... area that can help? The following works, but it seems a little explicit.

import Data.Maybe (mapMaybe)

graph :: (a -> b) -> [a] -> [(a, b)]
graph f = map (\x -> (x, f x))

liftMaybe :: (a, Maybe b) -> Maybe (a, b)
liftMaybe (x, Just y)  = Just (x, y)
liftMaybe (_, Nothing) = Nothing

partialgraph :: (a -> Maybe b) -> [a] -> [(a, b)]
partialgraph f = mapMaybe liftMaybe . graph f

Does liftMaybe exist with another name? I've found the following reformulations of some of these:

import Control.Monad (ap)

graph' :: (a -> b) -> [a] -> [(a, b)]
graph' = map . ap (,)

liftMaybe' :: (a, Maybe b) -> Maybe (a, b)
liftMaybe' (a, mb) = do
    b <- mb
    return (a, b)

liftMaybe'' :: (a, Maybe b) -> Maybe (a, b)
liftMaybe'' (a, mb) = fmap ((,) a) mb

liftMaybe''' :: (a, Maybe b) -> Maybe (a, b)
liftMaybe''' = uncurry (fmap . (,))

Answer 1

The simplest definition of liftMaybe would be

import Data.Traversable (sequenceA)

liftMaybe :: (a, Maybe b) -> Maybe (a, b)
liftMaybe = sequenceA

The documentation for sequenceA can be found here http://hackage.haskell.org/package/base/docs/Data-Traversable.html.

The general type signature is sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a), but in this case t is (,) c and f is Maybe.

Also, partialgraph could be expressed with traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) (which is also from Data.Traversable):

partialgraph :: (a -> Maybe b) -> [a] -> [(a, b)]
partialgraph f = mapMaybe $ \x -> traverse f (x, x)

or, if you prefer a little more pointlessness:

partialgraph f = mapMaybe (traverse f . join (,))

EDIT: When I wrote this answer, I didn't realize that the required Traversable and Foldable instances aren't defined in the GHC 7.6.3 standard library (they are in GHC 7.8 though). Here they are, courtesy of @robx:

instance Foldable ((,) a) where
  foldr f y (u, x) = f x y

instance Traversable ((,) a) where
  traverse f (u, x) = (,) u <$> f x

Answer 2

The simplest approach is probably to use a list comprehension:

partialGraph :: (a -> Maybe b) -> [a] -> [(a, b)]
partialGraph f xs = [(x, fx) | (x, Just fx) <- graph f xs]

This takes advantage of the failure semantics of pattern-matching in list comprehensions: if a pattern match fails, then that list element is skipped.¹

For instance,

ghci> partialGraph (\x -> if even x then Just $ x `quot` 2 else Nothing) [1..10]
[(2,1),(4,2),(6,3),(8,4),(10,5)]

There doesn't appear to be a liftSnd :: Functor f => (a, f b) -> f (a,b) function defined anywhere; uncurry $ fmap . (,) is about as concise as you're going to get.

If you define

preservingF :: Functor f => (a -> f b) -> a -> f (a, b)
preservingF = liftA2 fmap (,)

then you can use this function to define

partialGraph :: (a -> Maybe b) -> [a] -> [(a, b)]
partialGraph = mapMaybe . preservingF

which is pretty elegant, although the definition of preservingF is a little opaque (especially if you inline it).²

---

¹ This is just the (slightly questionable) fail (or the perfectly reasonable mzero) for the list monad, which simply produces the computation [].

² And just as you've been unable to find liftMaybe, I have been unable to find preservingF for a long time.

Answer 3

Hoogle returns nothing for (a,m b) -> m (a,b). So I guess the answer is no! There are a lot of similar functions which I've ended up implementing locally. The closest predefined example I can think of is sequence:

sequence :: Monad m => [m a] -> m [a]

But you can still hack your way to victory (using Data.Maybe and Control.Arrow):

graph f xs = map (second fromJust) $ filter (isJust . snd) $ zip xs $ map f xs