What are the steps for deducing this pointfree code?

Question

I was reviewing some code and came across the following gem, which I'd wager is a copy-paste of pointfree output:

(I thought the following would more appropriate than the usual foo/bar for this particular question :P)

import Control.Monad (liftM2)

data Battleship = Battleship { x :: Int
                             , y :: Int
                             } deriving Show

placeBattleship :: Int -> Int -> Battleship
placeBattleship x' y' = Battleship { x = x', y = y' }

coordinates :: Battleship -> (Int, Int)
coordinates = liftM2 (,) x y

Would someone be kind enough to explain the steps needed to simplify from:

(i) coordinates b = (x b, y b)

to:

(ii) coordinates = liftM2 (,) x y?

In particular, I'm a bit confused as to the use of liftM2 as I wasn't even aware that a monad was lurking in the background.

I know that (i) can also be represented as: coordinates s = (,) (x s) (y s) but I'm not sure where/how to proceed.

P.S. The following is why I suspect it's from pointfree (output is from GHCI and :pl is aliased to pointfree):

λ: :pl coordinates s = (x s, y s)
coordinates = liftM2 (,) x y

score 10 · Accepted Answer · edited May 23 '17 at 12:16

This takes advantage of the Monad instance for (->) r, also called the "reader monad". This is the monad of functions from a specific type to a. (Take a look here for motivation on why it exists in the first place.)

To see how it works for various functions, replace m with (r -> in m a. For example, if we just do liftM, we get:

liftM :: (a -> b) -> (m a -> m b)
liftM :: (a -> b) -> ((r -> a) -> (r -> b))
      :: (a -> b) -> (r -> a) -> (r -> b) -- simplify parentheses

...which is just function composition. Neat.

We can do the same thing for liftM2:

liftM2 :: (a -> b -> c) -> m a -> m b -> m c
liftM2 :: (a -> b -> c) -> (r -> a) -> (r -> b) -> (r -> c)

So what we see is a way to compose two one-argument functions with a two-argument function. It's a way of generalizing normal function composition to more than one argument. The idea is that we create a function that takes a single r by passing that through both of the one-argument functions, getting two arguments to pass into the two-argument function. So if we have f :: (r -> a), g :: (r -> b) and h :: (a -> b -> c), we produce:

\ r -> h (f r) (h r)

Now, how does this apply to your code? (,) is the two-argument function, and x and y are one-argument functions of the type Battleship -> Int (because that's how field accessors work). With this in mind:

liftM2 (,) x y = \ r -> (,) (x r) (y r)
               = \ r -> (x r, y r)

Once you've internalized the idea of multiple function composition like this, point-free code like this becomes quite a bit more readable—no need to use the pointfree tool! In this case, I think the non-pointfree version is still better, but the pointfree one isn't terrible itself.

score 5 · Answer 2 · answered Nov 19 '14 at 23:36

The monad liftM2 is working over here is the function monad (->) a. This is equivalent to the Reader monad, as you may have seen before.

Recall the definition of liftM2:

liftM2 :: Monad m => (a -> b -> r) -> m a -> m b -> m r
liftM2 f ma mb = do
    a <- ma
    b <- mb
    return $ f a b

So now if we substitute in (,) for f, x for ma, and y for mb, we get

liftM2 (,) x y = do
    a <- x
    b <- y
    return $ (,) a b

Since x, y :: Battleship -> Int which is equivalent to ((->) Battleship) Int, then m ~ (->) Battleship. The function monad is defined as

instance Monad ((->) a) where
    return x = const x
    m >>= f = \a -> f (m a) a

Essentially what the function monad does is allow you to extract the output from several functions provided they all have the same input. A more clear example might be something like

test = do
    a <- (^2)
    b <- (^3)
    c <- (^4)
    d <- show
    return (a, b, c, d)

> test 2
(4, 8, 16, "2")

score 1 · Answer 3 · answered Nov 20 '14 at 08:48

You could easily rewrite

data Battleship = Battleship { x :: Int
                             , y :: Int
                             } deriving Show

placeBattleship :: Int -> Int -> Battleship
placeBattleship x y = Battleship x y

coordinates :: Battleship -> (Int, Int)
coordinates  (Battleship x y) = (x, y)

It isn't point-free style, but quite simple

What are the steps for deducing this pointfree code?

3 Answers3