---

Panel 1: Introduction

I saw this meme post in r/haskell about point-free Haskell the other day. It’s meant to be sarcastic, I know, but there are actually some good ideas in it. So I might as well write a blog.

Per the meme, there are four ways to define mapM in terms of sequence and fmap. But actually, you only need to understand their definitions for Panel 1. All the rest can be derived from the first definition, each achieving the goal of point-free to some extent. For our purpose, let’s assume a function composed :: a -> b -> d can be defined in terms of f :: a -> b -> c and g :: c -> d. If we explicitly write out the arguments, then we get the first panel:

composed :: a -> b      -> d
f        :: a -> b -> c
g        ::           c -> d

composed a b = g (f a b)

So our goal can be restated as: to compose f and g, we first accept two arguments, then pass them to f, and finally forward the result to g. Or we can say, we want to wait for two arguments before forwarding the result.

A more familiar case is when we just want to wait for one argument.

composed' :: a      -> d
f'        :: a -> c
g'        ::      c -> d

composed' a = g' (f' a)

In this case, we have the usual function composition operator

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(g . f) a = g (f a)

Then it’s easy to see how we can make composed' point-free:

composed' a = (g' . f') a
composed'   =  g' . f'        -- η reduction

The problem, of course, is how to find a similar operator to wait for two arguments, or in general, wait for n arguments.

Panel 2: curry or uncurry, that is the question!

composed = curry (g . uncurry f)

Panel 2 uses curry and uncurry to bundle the two arguments together into a pair, then wait for the bundle with (.). When passing the bundle to f, we need to unbundle it.

Recall the definition of curry and uncurry:

curry   :: ((a, b) -> c) -> (a -> b -> c)
uncurry :: (a -> b -> c) -> ((a, b) -> c)

Then we can derive Panel 2:

                   f  :: a -> b -> c
           uncurry f  :: (a, b) -> c
       g              ::           c -> d
       g . uncurry f  :: (a, b)      -> d
curry (g . uncurry f) :: a -> b      -> d

This works fine for waiting for two arguments, but it’s not a good example for point-free style or abstraction because it

1. doesn’t separate the composition operator with the actual functions to be composed, they are instead intertwined together.
2. doesn’t generalize well if we want to wait for three or more arguments, we need to implement curry3 and uncurry3.

Therefore, we can’t read the intention of the code well. It doesn’t directly express the idea of waiting for two arguments.

Panel 3: Birds of a feather

composed = ((.).(.)) g f

The third panel seems promising, because it separates the operator and the functions, but what on earth is (.).(.)? (spoiler: it’s not on earth!)

I tried very hard to understand it the first time I met it. My current best explanation is as follows:

Recall the partial application of (.), we have (.) f ≡ (f .)(*).

At first, we have ((.).(.)) g f, so when (.).(.) gets the first argument g, what does it do?

Since it’s a composition of two functions, it will pass g to the latter function and forward the result to the former function.

That is (secondF . firstF) g ≡ secondF (firstF g). Here we take both secondF and firstF to be (.). Then

(secondF . firstF) g ≡ secondF (firstF g)
                     ≡ secondF ((.)    g)
                     ≡ secondF (g .)      -- see (*) above
                     ≡ (.)     (g .)
                     ≡ ((g .) .)          -- see (*) above

Then we apply it to the second argument f, we get ((.).(.)) g f ≡ (g .) . f.

How can we understand (g .) . f then?

Well, it’s a function composition. So when the first argument a comes, it will be passed to f, and the result will be forward to (g .).

(g .) . f $ a ≡ (g .) (f a)
              ≡  g .  (f a)

Then the second argument b comes, what will it do? Oh, it is again a function composition, so we pass b to the second function (f a), and then forward the result to g.

g . (f a) $ b ≡ g ((f a) b)
              ≡ g ( f a  b)

We achieved our goal.

This can also be understood through the type signature. After the first argument a comes to (g .) . f, it will be passed to f :: a -> b -> c, resulting in f a :: b -> c. Then we can just compose it with g :: c -> d with the usual (.).

So far, we have established that (g .) . f will wait for two arguments. Also, we know g . f will wait for one argument. Actually, these are special cases for a general pattern:

g . f         -- wait for 1 more argument
(g .) . f     -- wait for 2 more arguments
((g .) .) . f -- wait for 3 more arguments

Or equivalently, the operator style:

(.)         -- wait for 1 more argument
(.).(.)     -- wait for 2 more arguments
(.).(.).(.) -- wait for 3 more arguments

The type signatures will tell us what they do:

(.)         :: (d -> e) -> (          c -> d) -> (          c -> e)
(.).(.)     :: (d -> e) -> (     b -> c -> d) -> (     b -> c -> e)
(.).(.).(.) :: (d -> e) -> (a -> b -> c -> d) -> (a -> b -> c -> e)

Although presented in a meme, these are actually quite useful and common higher-order operators. Once you know them, they’re pretty easy to read, remember, and write.

(.).(.) is often presented as the first non-trivial example in these operators. It’s called a blackbird operator in Amar Shah’s talk about point-free, a dot in the Haskell wiki for point-free.

This family of operators is also an example for Semantic Editor Combinators in Edward Kmett’s talk about lenses.

Panel 4: One of them is not like the others

composed = fmap fmap fmap g f

In Panel 3, there are three points. BUt i thOught wE weRE DOing poINT-FREe PROGrAmMINg! So for Panel 4, we have three fmap and zero points. A reasonable guess would be that fmap is secretly (.). But how?

Recall their definitions:

(.)  ::              (b -> c) -> (a -> b) -> (a -> c)
fmap :: Functor f => (b -> c) -> (   f b) -> (   f c)

So here, we are instantiating the functor f to be (a ->). That is, we partially apply a fixed type a to (->), and change the return type variable, resulting in a (covariant) functor.

This functor is known as the Reader functor. We can explicitly define it as data Reader a x = Reader { runReader :: a -> x }. But in Haskell, we can just write ((->) a).

You can verify that its functor instance must be

instance Functor ((->) a) where
    fmap = (.)

You can read more about the Reader functor in this post from Bartosz’s blog.

Back to the meme, if we replace all (.) with fmap in Panel 3, then we get Panel 4.

It’s correct, but really confusing. Without looking at the signature, one can hardly imagine which instance is fmap using, let alone the intention of three fmap being together (the original meme also use fmap as an argument, just to be fun!).

There is, however, a chance to salvage something from Panel 4. Let’s think fmap fmap fmap in terms of itself, instead of being just (.) in disguise.

One way to type check fmap fmap fmap is to let the first fmap be instantiated to the Reader functor fmap, i.e. (.). Then fmap fmap fmap becomes (.) fmap fmap ≡ fmap . fmap.

The type signature can be derived as

fmap :: Functor f1 => (a -> b) -> (f1 a -> f1 b)
fmap :: Functor f2 =>             (c    -> d   ) -> (f2 c -> f2 d)

We can take c to be f1 a and d to be f1 b. Therefore

fmap        :: Functor f1               => (a -> b) -> (f1 a -> f1 b)
fmap        :: Functor f1               =>             (f1 a -> f1 b) -> f2 (f1 a) -> f2 (f1 b)
fmap . fmap :: (Functor f1, Functor f2) => (a -> b)                   -> f2 (f1 a) -> f2 (f1 b)

So by combining two fmap, we get one functor level deeper into the structure. This is another example of Semantic Editor Combinators also mentioned in the Kmett talk. The general case is:

fmap               :: (Functor f1)                         => (a -> b) -> f3 a           -> f3 b
fmap . fmap        :: (Functor f1, Functor f2)             => (a -> b) -> f3 (f2 a)      -> f3 (f2 b)
fmap . fmap . fmap :: (Functor f1, Functor f2, Functor f3) => (a -> b) -> f3 (f2 (f1 a)) -> f3 (f2 (f1 b))

We go one functor level deeper for each fmap composed. Keep digging this way, then you might find some lens for yourself!

Conclusion: What’s the point of point-free anyway?

The goal of the point-free style is the same as all other forms of abstraction: to express your intention in a concise (to write), clear (to read), and general (to change) way. All fore-mentioned methods can be summarized as follows:

(*): some experience required

Conclusions:

1. If you need clarity and don’t want to surprise others, go for Panel 1, write all arguments explicitly: composed a b = g (f a b).
2. Not every point-free change is guaranteed to be an improvement. You should avoid Panel 2 style (point-free for the sake of point-free) as much as possible. A point-free change should have a strong semantic encoding.
3. For Panel 3 and modified Panel 4, we can see the power of good point-free usage. We find a pattern ((.).(.) and fmap . fmap) with almost all of the advantages. However, they might be difficult to understand for those who are unfamiliar. And it takes a great deal of efforts to find a new one. Therefore, it’s good for in-house use.
4. For the original Panel 4, try not to hide your intention. Replace some instances of fmap with its concrete instance to avoid repetition and ambiguity (even just for humans).

---

Edit notes:

• The (.).(.) is called a blackbird, a special kind of bird. That is to say, it’s a special case of an operator in a family of operators. Thanks for Jean-Baptiste Mazon to point it out.