Numbers as multiplicative functions (weird but entertaining)

haskell

Solution

In an expression like `2 3 4` with your instances, both `2` and `3` are functions. So `2` is actually `(2 *)` and has a type `Num a => a -> a`. `3` is the same. `2 3` is then `(2 *) (3 *)` which is the same as `2 * (3 *)`. By your instance, this is `liftM2 (*) 2 (3 *)` which is then `liftM2 (*) (2 *) (3 *)`. Now this expression works without any of your instances.

So what does this mean? Well, `liftM2` for functions is a sort of double composition. In particular, `liftM2 f g h` is the same as `\ x -> f (g x) (h x)`. So `liftM2 (*) (2 *) (3 *)` is then `\ x -> (*) ((2 *) x) ((3 *) x)`. Simplifying a bit, we get: `\ x -> (2 * x) * (3 * x)`. So now we know that `2 3 4` is actually `(2 * 4) * (3 * 4)`.

Now then, why does `liftM2` for functions work this way? Let's look at the monad instance for `(->) r` (keep in mind that `(->) r` is `(r ->)` but we can't write type-level operator sections):

instance Monad ((->) r) where  
    return x = \_ -> x  
    h >>= f = \w -> f (h w) w  

So `return` is `const`. `>>=` is a little weird. I think it's easier to see this in terms of `join`. For functions, `join` works like this:

join f = \ x -> f x x

That is, it takes a function of two arguments and turns it into a function of one argument by using that argument twice. Simple enough. This definition also makes sense. For functions, `join` has to turn a function of two arguments into a function of one; the only reasonable way to do this is to use that one argument twice.

`>>=` is `fmap` followed by `join`. For functions, `fmap` is just `(.)`. So now `>>=` is equal to:

h >>= f = join (f . h)

which is just:

h >>= f = \ x -> (f . h) x x

now we just get rid of `.` to get:

h >>= f = \ x -> f (h x) x

So now that we know how `>>=` works, we can look at `liftM2`. `liftM2` is defined as follows:

liftM2 f a b = a >>= \ a' -> b >>= \ b' -> return (f a' b')

We can simply this bit by bit. First, `return (f a' b')` turns into `\ _ -> f a' b'`. Combined with the `\ b' ->`, we get: `\ b' _ -> f a' b'`. Then `b >>= \ b' _ -> f a' b'` turns into:

 \ x -> (\ b' _ -> f a' b') (b x) x

since the second `x` is ignored, we get: `\ x -> (\ b' -> f a' b') (b x)` which is then reduced to `\ x -> f a' (b x)`. So this leaves us with:

a >>= \ a' -> \ x -> f a' (b x)

Again, we substitute `>>=`:

\ y -> (\ a' x -> f a' (b x)) (a y) y

this reduces to:

 \ y -> f (a y) (b y)

which is exactly what we used as `liftM2` earlier!

Hopefully now the behavior of `2 3 4` makes sense completely.

Problem

Original source

Related problems

• Tacit function composition in Haskell