How does Haskell evaluate this function defined with partial application?

Question

I'm trying to understand how Haskell evalutes pp1 [1,2,3,4] to get [(1,2),(2,3),(3,4)] here:

1. xnull f [] = []
2. xnull f xs = f xs
3. (/:/) f g x = (f x) (g x)
4. pp1 = zip /:/ xnull tail

I start like this:

a)  pp1 [1,2,3,4] = (zip /:/ xnull tail) [1,2,3,4]  -- (rule 4).
b)  (zip /:/ xnull tail) [1,2,3,4] 
       = (zip (xnull [1,2,3,4]) (tail) [1,2,3,4])   -- (rule 3)
c)  -- I'm not sure how to continue because xnull receives a function 
    -- and a param, and in this case it only receives a param.

Any help?

Answer 1

Just keep expanding:

pp1 [1, 2, 3, 4] = zip /:/ xnull tail $ [1, 2, 3, 4]
                 -- inline (/:/) f g x = f x (g x)
                 --  f = zip, g = xnull tail, x = [1, 2, 3, 4]
                 -- therefore: 
                 = zip [1, 2, 3, 4] (xnull tail $ [1, 2, 3, 4])
                 -- inline the definition of xnull and note that the argument is not null
                 -- so we just want f x, or tail [1, 2, 3, 4]
                 = zip [1, 2, 3, 4] (tail [1, 2, 3, 4])
                 -- evaluate tail
                 = zip [1, 2, 3, 4] [2, 3, 4]
                 -- evaluate zip
                 = [(1, 2), (2, 3), (3, 4)]

Operator presidence matters. You didn't specify the associativity of (/:/) so it was defaulted to be relatively weak. Therefore, (xnull tail) bound tighter than (/:/).

Also, as a side note, (/:/) already exists in the standard library as (<*>) from Control.Applicative. It's sufficiently general so this might be difficult to see, but the Applicative instance for Reader (or perhaps better understood as the function Applicative) provides this exact instance. It's also known as ap from Control.Monad.

zip <*> tail :: [b] -> [(b, b)]
zip <*> tail $ [1, 2, 3, 4] = [(1, 2), (2, 3), (3, 4)]

Answer 2

This is wrong

b) (zip /:/ xnull tail) [1,2,3,4] = (zip (xnull [1,2,3,4]) (tail) [1,2,3,4]) (rule 3)

because it should be

b) (zip /:/ xnull tail) [1,2,3,4] = (zip [1,2,3,4] (xnull tail [1,2,3,4])) (rule 3)

The mistake lies in reading zip /:/ xnull tail as in (zip /:/ xnull) tail rather than zip /:/ (xnull tail).

Answer 3

I know this has got a bit old. But anyway, here's my take..

It helps to see the definition

pp1 =  zip  /:/  xnull tail
    = (zip) /:/ (xnull tail)
    = (/:/) zip (xnull tail)

Note the parenthesizes around (xnull tail) indicating function application having higher precedence the infix operators.

Now the definition of (/:/) is to return another function q that would take an argument x and return the result of applying the function returned by partially applying its first argument r to what is returned from applying its second argument s.

That is f would need to be able to take at least 2 arguments, while g need only take at least 1.

(/:/) f g = q 
            where
            q x = r s
                  where
                  r = f x
                  s = g x

Note that r is f x, so q x is f x s.

It would have been clearer to write

f /:/ g = (\x -> f x (g x))

Now given

pp1 = zip /:/ xnull tail 

we can expand to

pp1 = q
      where
      q x = r s
            where
            r = zip x
            s = xnull tail x

or

pp1 = (\x -> zip x $ xnull tail x)

The rest is just replacing x with [1,2,3,4] and do the evaluations.