How does ap fromMaybe compose?

Question

There I was, writing a function that takes a value as input, calls a function on that input, and if the result of that is Just x, it should return x; otherwise, it should return the original input.

In other words, this function (that I didn't know what to call):

foo :: (a -> Maybe a) -> a -> a
foo f x = fromMaybe x (f x)

Since it seems like a general-purpose function, I wondered if it wasn't already defined, so I asked on Twitter, and Chris Allen replied that it's ap fromMaybe.

That sounded promising, so I fired up GHCI and started experimenting:

Prelude Control.Monad Data.Maybe> :type ap
ap :: Monad m => m (a -> b) -> m a -> m b
Prelude Control.Monad Data.Maybe> :type fromMaybe
fromMaybe :: a -> Maybe a -> a
Prelude Control.Monad Data.Maybe> :type ap fromMaybe
ap fromMaybe :: (b -> Maybe b) -> b -> b

The type of ap fromMaybe certainly looks correct, and a couple of experiments seem to indicate that it has the desired behaviour as well.

But how does it work?

The fromMaybe function seems clear to me, and in isolation, I think I understand what ap does - at least in the context of Maybe. When m is Maybe, it has the type Maybe (a -> b) -> Maybe a -> Maybe b.

What I don't understand is how ap fromMaybe even compiles. To me, this expression looks like partial application, but I may be getting that wrong. If this is the case, however, I don't understand how the types match up.

The first argument to ap is m (a -> b), but fromMaybe has the type a -> Maybe a -> a. How does that match? Which Monad instance does the compiler infer that m is? How does fromMaybe, which takes two (curried) arguments, turn into a function that takes a single argument?

Can someone help me connect the dots?

Answer 1

But that use of ap is not in the context of Maybe. We're using it with a function, fromMaybe, so it's in the context of functions, where

ap f g x = f x (g x)

Among the various Monad instances we have

instance Monad ((->) r)

so it is

ap :: Monad m =>    m  (a       -> b)  ->    m  a  ->    m  b
fromMaybe     ::  r -> (Maybe r -> r)
ap            :: (r -> (a       -> b)) -> (r -> a) -> (r -> b)   
ap                   f                        g        x :: b
ap  fromMaybe ::                          (r -> a) -> (r -> b)  , a ~ Maybe r , b ~ r

because -> in types associates to the right: a -> b -> c ~ a -> (b -> c). Trying to plug the types together, we can only end up with that definition above.

And with (<*>) :: Applicative f => f (a -> b) -> f a -> f b, we can write it as (fromMaybe <*>), if you like this kind of graffiti:

 #> :t (fromMaybe <*>)
(fromMaybe <*>) :: (r -> Maybe r) -> r -> r

---

As is rightfully noted in another answer here, when used with functions, <*> is just your good ole' S combinator. We can't very well have function named S in Haskell, so <*> is just a part of standard repertoire of the point-free style of coding. Monadic bind (more so, flipped), =<<, can be even more mysterious, but a pointfree coder just doesn't care and will happily use it to encode another, similar pattern,

(f =<< g) x = f (g x) x 

in combinatory function calls, mystery or no mystery (zipWith (-) =<< drop 1 comes to mind).