1

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?

Improve this question
1
  • xnull tail == drop 1, (/:/) == Control.Applicative.(<*>). Commented Sep 20, 2014 at 17:05

3 Answers 3

Reset to default
4

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)]
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

I have a doubt. Why is wrong this? /:/ xnull tail [1,2,3,4] = xnull [1,2,3,4] (tail) [1,2,3,4] if I consider f as xnull, g as tail and x as [1,2,3,4]? Thanks again!
Because of how function binding works. xnull tail binds more tightly than (/:/ xnull). The reason is simply operator precedence rules -- function application (i.e. xnull tail) binds more tightly than operator application (i.e. (/:/ xnull)). You have some control over this, but that should only be exercised very carefully.
Ok, I understand that precedence is important for expression evaluation. But what I don't understand are the expressions for f, g, and x when you apply rule number 3, f = ?, g = ? and x = ? Thanks again!
Oh! that's a simpler question. f = zip, g = xnull tail, and x = [1, 2, 3, 4].
Ok, updated my answer to explain the transformations I made in more detail.
4

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).

Improve this answer

4 Comments

Why don't you need a $ to get the zip /:/ (xnull tail) interpretation?
Because application binds more tightly than any infix operator: f x ++ g x is read as (f x) ++ (g x), and x ++**++ f x is read as (x) ++**++ (f x). Note that $ follows this parsing rule, and /:/ does as well.
@chi I have a doubt. Why is wrong this? /:/ xnull tail [1,2,3,4] = xnull [1,2,3,4] (tail) [1,2,3,4] if I consider f as xnull, g as tail and x as [1,2,3,4]? Thanks again!
@Seba There's no /:/ xnull tail [1,2,3,4] in the first place because (zip /:/ xnull tail) means (zip /:/ (xnull tail)), because as chi points out, function application binds most tightly.
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.