Haskell - redundant part in function

Question

I have an intricate Haskell function:

j :: [Int]
j = ((\f x -> map x) (\y -> 3 + y) (\z -> 2*z)) [1,2,3]

My guess was that (\y -> 3 + y) (\z -> 2*z) will change to (\w -> 3 + 2*w) and together with f there should be print out the list [5,7,9].

When I checked with ghci I got [2,4,6] as a result.

Question: So is (\y -> 3 + y) a redundant expression here? If so, why?

Answer 1

I think you've gone wrong somewhere in the design of your function, but I'll give you an explanation of the mechanics going on here. Stick around for the detailed explanation if you still get stuck understanding.

Quick answer: Evaluating the expression

j = ((\f x -> map x) (\y -> 3 + y) (\z -> 2*z)) [1,2,3]
  = ((\x -> map x) (\z -> 2*z)) [1,2,3]
  = (map (\z -> 2*z)) [1,2,3] -- f := (\y -> 3 + y), x := (\z -> 2*z)
  = [2,4,6]

You may see that when Haskell evaluates (\f x -> map x) (\y -> 3 + y), which it will because function applications are evaluated left-to-right, the substitution f := (\y -> 3 + y) is made, but f doesn't appear anywhere in the function, so it just becomes (\x -> map x).

Detailed answer: Left (and Right) associative operators

In Haskell we say that function application is left associative. This is to say, when we write a function application, it is evaluated like so:

function arg1 arg2 arg3 = ((function arg1) arg2) arg3

No matter what the types of the arguments are. This is called left associative because the brackets are always on the left.

You seem to expect your expression to behave like this:

  (\f x -> map x) (\y -> 3 + y) (\z -> 2*z)
= (\f x -> map x) ((\y -> 3 + y) (\z -> 2*z)) -- Incorrect

However, as we've seen, functions associate left, not right as you assumed, and so your expression looks to Haskell like this:

  (\f x -> map x) (\y -> 3 + y) (\z -> 2*z)
= ((\f x -> map x) (\y -> 3 + y)) (\z -> 2*z)
= (\x -> map x) (\z -> 2*z)                   -- Correct!

Notice that the brackets I put in to order the evaluation are on the left, not the right.

However, Haskell has defined a very useful right-associative function application operator, namely ($) :: (a -> b) -> a -> b. You could re-write your expression like so to obtain the result you seemed to expect.

  (\f x -> map x) $ (\y -> 3 + y) (\z -> 2*z)
= (\f x -> map x) $ ((\y -> 3 + y) (\z -> 2*z)) -- Correct, though nonsensical.

However, as you'll notice, f still isn't referred to in (\f x -> map x) and so is ignored entirely. I'm not sure exactly what your goal was in making this function

Further issue: Lambda expressions & composition

I realise that another issue may be your understanding of lambda expressions. Consider this function:

f x = x + 2

We could re-write this as a lambda expression, like so:

f = \x -> x+2

However, what if we have two arguments? This is what we do:

g x y = x + y

g = \x -> (\y -> x+y)

The way Haskell models multiple arguments is called currying. You can see that the function actually returns another function, which then returns a function that finally returns what it should have. However, this notation is long and cumbersome, so Haskell provides an alternative:

g = \x y -> x + y

This may seem to be different, but in fact it is syntactic sugar for exactly the same expression as before. Now, looking at your first lambda expression:

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

You can see that the argument f isn't actually referred to at all in the function, so if I apply something to it:

  (\f x -> map x) foo
= (\f -> (\x -> map x)) foo
= \x -> map x

That's why your (\y -> 3 + y) is ignored; you haven't actually used it in your functions.

Furthermore, you expect the expression (\y -> 3 + y) (\z -> 2*z) to evaluate to \w -> 3 + 2*w. This is not true. The lambda on the left replaces each occurrence of y with (\z -> 2*z), so the result is the completely nonsensical 3 + (\z -> 2*z). How do you add a function to a number?!

What you're looking for is called composition. We have an operator in Haskell, namely (.) :: (b -> c) -> (a -> b) -> (a -> c) which can help you with this. It takes a function on the left and the right and creates a new function that 'pipes' the functions into each other. That is to say:

(\y -> 3 + y) . (\z -> 2*z) = \w -> 3 + 2*w

Which is what you're looking for.

Conclusion: Corrected expression

I think the expression you're looking for is:

j = ( (\x -> map x) $ (\y -> 3 + y) . (\z -> 2*z) ) [1,2,3]

Which is equivalent to saying:

j = map (\w -> 3 + 2*w) [1,2,3]

Since you seem to be having a lot of trouble with the more basic parts of Haskell, I'd recommend the quintessential beginner's book, Learn You a Haskell for Great Good.

Answer 2

It is because it goes the other way round, that is you apply (\f x -> map x) to (\y -> 3 + y) first. But

(\f x -> map x) something g

becomes

let f = something; x = g in map x

And this finally is

map g

So something doesn't appear in the resulting expression, since f is not mentioned anywhere right from the arrow.

If I understand you correctly, you want

(\f x -> map (f . x))

Additional note: From your argumentation, it looks like you have not grasped yet how beta reduction works.

For example, even if the expressions would be applied like you think:

(\y -> 3 + y) (\z -> 2*z)

the result would be

3 + (\z -> 2*z)

No, it is doubtful that this makes any sense, however, it's the way beta reduction works: It gives the part right from the arrow where every occurrence of a parameter is replaced by the actual argument.