Fun with Function Application (Haskell version)

FuncApplicationHaskell.md

Fun with Function Application (Haskell version)

Function application operators in Haskell make programming more understandable and help reduce parenthesis.

($)

The application operator, $, can be used to reduce the need for parenthesis. The following:

f (g x)

can be rewritten as:

f $ g x

reducing the noisy parenthesis.

This function is defined in Prelude as:

($) :: (a -> b) -> a -> b
f $ x = f x

(&)

The reverse application operator, &, is even more useful allowing us to write code as a Data Flow.

The following:

map (* 10) $ filter (2 <) [1, 2, 3, 4, 5]

can be rewritten as:

[1, 2, 3, 4, 5]
  & filter (2 <)
  & map (* 10)

making the code easier to follow.

This function is defined in Data.Function as:

(&) :: a -> (a -> b) -> b
x & f = f x

Alternative implementations

Let's rewrite these operators in prefix order:

($) :: (a -> b) -> a -> b
($) f x = f x

(&) :: a -> (a -> b) -> b
(&) x f = f x

& is just the flip of $ as can be seen by the type signatures.

So let's rewrite & in terms of $:

(&) :: a -> (a -> b) -> b
(&) = flip ($)

And now time for something completely unexpected

The unexpected

Let's eta-reduce $ by first eliminating the x on both right-hand sides:

($) :: (a -> b) -> a -> b
($) f = f

We recognize our reduced function as just id, takes an f and returns an f. So let's refactor with that fact:

($) :: (a -> b) -> a -> b
($) = id

We could've also infered this by just considered the type signature and by added in the implied right-hand parenthesis giving us:

(a -> b) -> (a -> b)

which is equivalent to a -> a the type signature for id.

One very important thing to keep in mind is that the type signature for $ keeps it from being used in place of id in your code.

You could say the $ is id for functions ONLY.

The fact that $ is just id was unexpected but makes sense.

The unexpected and baffling

Since (&) is just the flip of ($), we can rewrite it as:

(&) :: a -> (a -> b) -> b
(&) = flip id

But wait! This is both unexpected and, at first glance, doesn't make sense.

The baffling thing is that flip has the following implementation in Prelude:

flip :: (a -> b -> c) -> b -> a -> c
flip f x y = f y x

which says that flip takes as its first parameter a function of 2 parameters.

But id takes only 1 parameter! So then how can you flip a function with only 1 parameter???

Clarity

The lack of redundant parenthesis can sometimes make type signatures difficult to reason about.

For example, take the type signature for $:

($) :: (a -> b) -> a -> b

When we added in the redundant, right-side parenthesis:

($) :: (a -> b) -> (a -> b)

it instantly became obvious that $ is just id.

But our confusion above is with &:

(&) :: a -> (a -> b) -> b
(&) = flip id

All of our substitutions that got us here were valid and this code compiles but it's just not intuitive as to how flip combines with id.

So once again, let's add in the implied right-assosiative parenthesis to the first parameter of flip:

flip :: (a -> (b -> c)) -> b -> a -> c
flip f x y = f y x

Written this way, which is equivalent to without the parenthesis, it appears that the first parameter is a function of 1 parameter!

This can be confusing even if you've seen this before. Coming from non-curried languages, it's easy to think in terms of multiple parameters. But that's where our thinking can go astray.

For example, we can take the following:

a -> b -> c -> d

and just by adding parenthesis, make it look like the function takes 1, 2, or 3 parameters:

a -> b -> c -> d   -- 3 parameters
a -> b -> (c -> d) -- 2 parameters
a -> (b -> c -> d) -- 1 parameter

But all functions ONLY take 1 parameter!!! That's what Currying is all about.

So the objection about passing id to flip because the first parameter of flip takes 2 parameters is wrong!

With this in mind, let's look at flip with the extra parenthesis:

flip :: (a -> (b -> c)) -> b -> a -> c
flip f x y = f y x

and id:

id :: a' -> a'
id x = x

We can apply flip to id and figure out its type signature.

The first parameter of flip is id which means that the types must be equivalent and line up:

a' ->    a'      -- id
a  -> (b -> c)   -- flip's first parameter

which means:

a' = a
a' = (b -> c)

which then means:

a = (b -> c)

since they both equal a'.

Now we're ready to determine the type signature for flip id.

First let's return to the type signature for flip and remove the first parameter since we have given it id as the first parameter AND let's also replace a with (b -> c):

flip    :: (a -> (b -> c)) -> b ->    a     -> c
flip id ::                    b -> (b -> c) -> c

Comparing signatures for flip id and & shows that they're equivalent:

flip id :: b' -> (b' -> c) -> c
(&)     :: a  -> (a  -> b) -> b

where b' = a and b = c.

Lessons learned

It's easy but sometimes problematic to think of:

a -> b -> c

as a function of 2 parameters when in fact it's really:

a -> (b -> c)

which is clearly a function of only 1 parameter.

As is:

a -> b -> c -> d -> e -> f

since it's really:

a -> (b -> (c -> (d -> (e -> f))))

which is function of only 1 parameter also.

Ask a Haskell programmer, what does flipping id look like and they'll probably scratch their heads and think "Why would you need to flip id?" or "Wait, you can't do that! Flip swaps the first 2 parameters and id only has 1."

I know that I did.

But as we've seen, you can. It's the way we typically think about flip that's wrong.