How does the flip function work?

40
votes

Haskell newbie here. I was going through Learn you a haskell, and came across this definition of the flip function.

flip' :: (a -> b -> c) -> (b -> a -> c)  
flip' f = g  
    where g x y = f y x

What I don't get is, where did x and y come from? I mean, the signature tells me that flip' is a function that takes a function (with two parameters), and returns a function (again, with two parameters).

If I'm understanding this right, when I write a function which goes like

foo :: (a -> b) -> a -> b
foo f x = f x   -- applies the function f on x

But then, in this case I'm passing the parameter explicitly [ ie x ] and so I'm able to access it in the function body. So how come the flip' function can access the parameters x and y?

5
haskell
Do you know that (a -> b) -> a -> b and (a -> b) -> (a -> b) are equivalent? – user824425
Equivalent because -> operator associates to the right? Similar to how I can write a -> (b -> c) as a -> b -> c. – ersran9
Exactly. I thought it would help to see that foo f x = f x is the same as foo f = f (given the same type signature). Anyway, those parameters x and y you mention are bound in the definition of g, that's where they come from. The definition of g can also be written as g = (\x y -> f y x). This means that flip' could also be defined as flip' f = (\x y -> f y x), which is equivalent to flip' f x y = f y x. This is in a way related to the right-associativity of (->). – user824425

5 Answers

43
votes

The Prelude, which is in the base package at hackage.haskell.org, is included with an implicit import in every Haskell file is where the flip function is found. On the right side you can click "source" and see the source code for flip.

flip         :: (a -> b -> c) -> b -> a -> c
flip f x y   =  f y x

The where clause allows for local definitions, x=10 or y="bla". You can also define functions locally with the same syntax you would for the top level. add x y = x + y

In the below equivalent formulation I make the substitution g = f y x

flip         :: (a -> b -> c) -> b -> a -> c
flip f x y   =  g
  where
    g = f y x

Right now g takes no parameters. But what if we defined g as g a b = f b a well then we would have:

flip         :: (a -> b -> c) -> b -> a -> c
flip f x y   =  g x y
  where
    g a b = f b a

No we can do a little algebraic cancelation(if you think of it like algebra from math class you will be pretty safe). Focusing in on:

flip f x y   =  g x y

Cancel the y on each side for:

flip f x   =  g x

Now cancel the x:

flip f   =  g

and now to put it back in the full expression:

flip     :: (a -> b -> c) -> b -> a -> c
flip f   =  g
  where
    g a b = f b a

As a last cosmetic step we can make the substitution a to x and b to y to recover the function down to argument names:

flip     :: (a -> b -> c) -> b -> a -> c
flip f   =  g
  where
    g x y = f y x

As you can see this definition of flip is a little round about and what we start with in the prelude is simple and is the definition I prefer. Hope that helps explain how where works and how to do a little algebraic manipulation of Haskell code.

16
votes

flip' doesn't access x and y. It receives an argument f, and evaluates to the expression g. No x or y in sight.

However, g is itself a function, defined with an auxiliary equation in the where clause of flip'.

You can read g x y = f y x exactly as if it were a top level equation like flip'. So g is a function of two arguments, x and y. It's g that has access to x and y, not flip'. Values for those arguments don't exist until g is applied, which is not until after flip' has returned the function g (if ever).

The thing that's special that about g being defined in the where clause of flip' is that it can have access to the arguments of flip', which is how g can be defined in terms of f.

So when flip' is invoked it receives a function f. For each particular invocation of flip', it constructs a new function g. g would receive two arguments, x and y, when it is called, but that hasn't happened yet. flip' then just returns g as its result.

1
votes

Let's find the type of g.

We know flip type : (a -> b -> c) -> (b -> a -> c)

Therefore we can deduce f type : (a -> b -> c)

We have this definition for g

g x y = f y x

From the right-hand-side we deduce that y :: a and x :: b.

Hence g :: b -> a -> c

Note that the definition could be rewritten without the 'where' clause. 

flip' f = g where g x y = f y x
-> flip' f a b = g a b where g a b = f b a
-> flip' f a b = f b a
1
votes

Put simply, you can also define functions in a where block. So the variables x and y are just the formal parameters of g, and that's why you can access it in g x y = f y x: g x y defines formal parameters x and y, and f y x is the definition of what g does. Finally, that definition is returned from flip f = g.

1
votes

One simple example to understand and illustrate, on your ghci do:

Prelude> sub x y = x - y
Prelude> sub 3 1
2
Prelude> flip sub 3 1
-2