How does the expression `ap zip tail` work

问题:

I wondered how to write f x = zip x (tail x) in point free. So I used the pointfree program and the result was f = ap zip tail. ap being a function from Control.Monad

I do not understand how the point free definition works. I hope I can figure it out if I can comprehend it from the perspective of types.

import Control.Monad (ap)
let f = ap zip tail
let g = ap zip
:info ap zip tail f g
ap :: Monad m => m (a -> b) -> m a -> m b
    -- Defined in `Control.Monad'
zip :: [a] -> [b] -> [(a, b)]   -- Defined in `GHC.List'
tail :: [a] -> [a]      -- Defined in `GHC.List'
f :: [b] -> [(b, b)]    -- Defined at <interactive>:3:5
g :: ([a] -> [b]) -> [a] -> [(a, b)]
    -- Defined at <interactive>:4:5

By looking at the expression ap zip tail I would think that zip is the first parameter of ap and tail is the second parameter of ap.

Monad m => m (a -> b) -> m a -> m b
           \--------/   \---/
              zip        tail

But this is not possible, because the types of zip and tail are completely different than what the function ap requires. Even with taking into consideration that the list is a monad of sorts.

回答1:

So the type signature of ap is Monad m => m (a -> b) -> m a -> m b. You've given it zip and tail as arguments, so let's look at their type signatures.

Starting with tail :: [a] -> [a] ~ (->) [a] [a] (here ~ is the equality operator for types), if we compare this type against the type of the second argument for ap,

 (->) [x]  [x] ~ m a
((->) [x]) [x] ~ m a

we get a ~ [x] and m ~ ((->) [x]) ~ ((->) a). Already we can see that the monad we're in is (->) [x], not []. If we substitute what we can into the type signature of ap we get:

(((->) [x]) ([x] -> b)) -> (((->) [x]) [x]) -> (((->) [x]) b)

Since this is not very readable, it can more normally be written as

  ([x] -> ([x] -> b)) -> ([x] -> [x]) -> ([x] -> b)
~ ([x] ->  [x] -> b ) -> ([x] -> [x]) -> ([x] -> b)

The type of zip is [x] -> [y] -> [(x, y)]. We can already see that this lines up with the first argument to ap where

[x]         ~    [x]   
[y]         ~    [x]   
[(x, y)]    ~    b

Here I've listed the types vertically so that you can easily see which types line up. So obviously x ~ x, y ~ x, and [(x, y)] ~ [(x, x)] ~ b, so we can finish substituting b ~ [(x, x)] into ap's type signature and get

([x] -> [x] -> [(x, x)]) -> ([x] -> [x]) -> ([x] -> [(x, x)])
--   zip                        tail        ( ap  zip  tail )
--                                            ap  zip  tail u = zip u (tail u)

I hope that clears things up for you.

EDIT: As danvari pointed out in the comments, the monad (->) a is sometimes called the reader monad.

回答2:

There are two aspects to understanding this:

1. The type magic
2. The information flow of the implementation

Firstly, this helped me understand the type magic:

1) zip          : [a] → ( [a] → [(a,a)] )
2) tail         : [a] → [a]
3) zip <*> tail : [a] → [(a,a)]

4) <*> : Applicative f ⇒ f (p → q) → f p → f q

In this case, for <*>,

5) f x = y → x

Note that in 5, f is a type constructor. Applying f to x produces a type. Also, here = is overloaded to mean equivalence of types.

y is currently a place-holder, in this case, it is [a], which means

6) f x = [a] -> x

Using 6, we can rewrite 1,2 and 3 as follows:

7) zip          : f ([a] → [(a,a)])
8) tail         : f [a]
9) zip <*> tail : f ([a] → [(a,a)])  →  f [a]  →  f [(a,a)]

So, looking at 4, we are substituting as follows:

10) p = [a]
11) q = [(a,a)]
12) f x =  [a] → x

(Repetition of 6 here again as 12 )

Secondly, the information flow, i.e. the actual functionality. This is easier, it is clear from the definition of <*> for the Applicative instance of y →, which is rewritten here with different identifier names and using infix style:

13) g <*> h $ xs = g xs (h xs)

Substituting as follows:

14) g = zip
15) h = tail

Gives:

zip <*> tail $ xs        (Using 14 and 15)
  ==
zip xs (tail xs)         (Using 13 )