How does this let expression work?

Question

Given this line of Haskell code, my task was to evaluate it to its most simple form.

let g h k = (\x -> k (h x)) in g (+1) (\x -> x+x) 20

I have already been given the answer (and of course evaluated it myself in GHCI): 42

However, I would like get a better understanding of how the evaluation actually works here. In general, I think I know how (simple) let expressions work:

Example

a = let y = 5 in y * 5  -- a == 25

This evaluates to 25 because we bind y to the value of 5 and a gets assigned to the value of y*5 (the part after the in). The binding y = 5 is only valid within the scope of the let.

So far, the only interpretation (which at least evaluates to 42) is the following:

let g h k = (\x -> k (h x)) in g (+1) (\x -> x+x) 20

• g is (\x -> k (h x))
• h is (+1) (the function (\x -> x+1))

• k is (\x -> x+x)

  1. 20 is the input of g which yields k (h 20)
  2. h 20 gives 20 + 1 = 21
  3. k (h 20) = k 21 = 21 + 21 = 42

But what confuses me is the use of g h k after the let. What does that mean?

Answer 1

Think of a function definition. If you write:

g h k x = k (h x)

Then it is a function that takes three parameters h, k and x and returns k (h x). This is equivalent to:

g h k = \x -> k (h x)

or:

g h = \k x -> k (h x)

or:

g = \h k x -> k (h x)

So we can transfer variables between the head of the function, and the lambda-expression in the body. In fact a Haskell compiler will rewrite it.

So with the let expression, we define a locally scoped function like the one defined above. Now if we call g (+1) (\x -> x+x) 20, then will thus call g with h = (+1), k = (\x -> x+x) and x = 20.

So we will evaluate it as:

(\x -> x+x) ((+1) 20)

which evaluates to:

   (\x -> x+x) ((+1) 20)
-> ((+1) 20)+((+1) 20)
-> 21 + 21
-> 42