Confusion about currying and point free style in Haskell

Question

I was trying to implement the function

every :: (a -> IO Bool) -> [a] -> IO Bool

which was the topic for this question. I tried to do this without explicit recursion. I came up with the following code

every f xs = liftM (all id) $ sequence $ map f xs

My function didn't work since it wasn't lazy (which was required in the question), so no upvotes there :-).

However, I did not stop there. I tried to make the function point-free so that it would be shorter (and perhaps even cooler). Since the arguments f and xs are the last ones in the expression I just dropped them:

every = liftM (all id) $ sequence $ map

But this did not work as expected, in fact it didn't work at all:

    [1 of 1] Compiling Main             ( stk.hs, interpreted )

    stk.hs:53:42:
        Couldn't match expected type `[m a]'
               against inferred type `(a1 -> b) -> [a1] -> [b]'
        In the second argument of `($)', namely `map'
        In the second argument of `($)', namely `sequence $ map'
        In the expression: liftM (all id) $ sequence $ map
    Failed, modules loaded: none.

Why is that? I was under the impression that it was possible to simply drop trailing function arguments, which basically is what currying is about.

Answer 1

The definition of $ is

f $ x = f x

Let's fully parenthesize your function:

every f xs = (liftM (all id)) (sequence ((map f) xs))

and your curried version:

every = (liftM (all id)) (sequence map)

As you noticed, these are not identical. You can only drop trailing function arguments when they are the last thing applied. For example,

f x = g c x

is actually

f x = (g c) x

and the application of (g c) to x comes last, so you can write

f = g c

One pattern with the application operator $ is that it often becomes the composition operator . in points-free versions. This is because

f $ g $ x

is equivalent to

(f . g) $ x

For example,

every f xs = liftM (all id) $ sequence $ map f xs

can become

every f xs = (liftM (all id) . sequence . map f) xs

at which point you can drop xs:

every f = liftM (all id) . sequence . map f

Eliminating the argument f is more difficult, because it is applied before the composition operator. Let's use the definition of dot from http://www.haskell.org/haskellwiki/Pointfree:

dot = ((.) . (.))

With points, this is

(f `dot` g) x = f . g x

and is exactly what we need to make every fully points-free:

every = (liftM (all id) . sequence) `dot` map

Sadly, due to restrictions in the Haskell type system, this one needs an explicit type signature:

every :: (Monad m) => (a -> m Bool) -> [a] -> m Bool