Error when trying to compose monadic functions

Question

I just learned about monads, and I've been trying to implement a lot of the functions in Control.Monad. I just got to ap, but I can't make it work. I made a function almostAp :: Monad m => m (a -> b) -> m a -> m (m b), and I tried to compose it with another function I made, flatten :: Monad m => m (m b) -> m b. The problem is when I try to use ap = flatten . almostAp, I get

Occurs check: cannot construct the infinite type: m ~ (->) (m a)
  Expected type: m (a -> b) -> m a -> m a -> m b
  Actual type: m (a -> b) -> m a -> m (m b)
In the second argument of ‘(.)’, namely ‘almostAp’
In the expression: (flatten . almostAp)`

But, (flatten .) has type Monad m => (a -> m (m b)) -> a -> m b according to ghci, so why does this happen?

Here are the function definitions (I know I can clean them up with =<< and the functor laws):

almostAp :: Monad m => m (a -> b) -> m a -> m (m b)
almostAp = (flip (\x -> fmap ($x))) . (fmap (flip (>>=))) . (fmap (return .))

flatten :: Monad m => m (m a) -> m a
flatten = (>>= id)

You seem very keen on point-free style, which makes your code rather hard to read (and, I can imagine, rather hard to write, too!) Don't be afraid of `let` bindings or `do` notation. — Benjamin Hodgson, Apr 10 '16 at 23:51
"`let` go of point-free style: only use it `where` it makes sense, and you will `do` better" — Cactus, Apr 11 '16 at 06:46

score 5 · Accepted Answer · edited Jun 25 '19 at 09:37

You were getting your type error because you were trying to compose a one-argument function flatten (which, incidentally, usually goes by the name of join) with a two-argument function almostAp. (.) :: (b -> c) -> (a -> b) -> (a -> c) is meant for when the function on the right is a one-argument function. Unfortunately the error message was not very helpful.

(.).(.) (pronounced "dot-dot-dot", or "owl eyes") does what you want:

ghci> let ap = ((.).(.)) flatten almostAp
ghci> :t ap
ap :: Monad m => m (a -> b) -> m a -> m b

But ap can be implemented much more simply with do notation. Is your version really easier to understand than this?

ap mf mx = do
    f <- mf
    x <- mx
    return (f x)

do notation is just syntactic sugar for >>=. Here's how it looks without it (though I much prefer the do version):

ap mf mx = mf >>= \f -> fmap f mx

`(.).(.)` is "owl eyes" in my mind, which seems rather more ... family friendly. — dfeuer, Apr 11 '16 at 04:28

score 3 · Answer 2 · edited May 23 '17 at 11:52

But, (flatten .) has type Monad m => (a -> m (m b)) -> a -> m b according to ghci, so why does this happen?

Indeed, it does. Consider:

flatten  :: Monad m => m (m a) -> m a

almostAp :: Monad m => m (a -> b) -> m a -> m (m b)

Thus, the type of (flatten .) is:

flatten     :: Monad m => m (m a) -> m a -- renaming a to b
                          |     |    | |
                          -------    ---
                             |        |
(.)         ::              (b    ->  c) -> (a ->    b)    -> a ->  c
                                                     |              |
                                                  -------          ---
                                                  |     |          | |
(flatten .) :: Monad m =>                   (a -> m (m b)) -> a -> m b

However, you can't apply (flatten .) to almostAp because the types are incompatible:

almostAp    :: Monad m => m (a -> b) -> m a -> m (m b)
                          |        |    |            |
                          ----------    --------------
                               |               |
                               |            -------
                               |            |     |
(flatten .) :: Monad m => (    a     ->     m (m b))   -> a -> m b

You expected this:

almostAp    :: Monad m => m (a -> b) -> m a -> m (m b)
                          |               |    |     |
                          -----------------    -------
                                  |               |
                                  |            -------
                                  |            |     |
(flatten .) :: Monad m => (       a         -> m (m b)) -> a -> m b

But, that's not the way currying works. A function of the type a -> b -> c means a -> (b -> c) and not (a -> b) -> c. The first function a -> (b -> c) takes two arguments¹, a and b, and returns c. The second function (a -> b) -> c takes one argument a -> b and returns c.

So, how do you compose flatten and almostAp? You can't do it using normal function composition because almostAp requires two arguments:

(.) :: (b -> c) -> (a -> b) -> a -> c
       |      |    |      |
       --------    --------
           |           |
        flatten        +-- almostAp can't be used because it needs two arguments
                        -- but (.) only gives it one argument (the `a` in a -> b)

We need a special composition operator to compose them:

(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
        |      |    |           |
        --------    -------------
            |             |
         flatten      almostAp

(.:) f g x y = f (g x y)

Now, we can simply write flatten .: almostAp. Another way to write it would be (flatten .) . almostAp. This is because (.:) = (.) . (.). Read the following for more details:

What does (f .) . g mean in Haskell?

¹ Actually, a function of the type a -> (b -> c) only takes one argument a and returns another function b -> c which takes the second argument b and returns c.

Error when trying to compose monadic functions

2 Answers2