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

Answer 2

g h k = ... is a function definition. It means that the result of applying g to two arguments (named h and k) will evaluate to the ... part. In other words it's a shortcut for g = \h -> \k -> ....

So we can simplify the expression step by step as follows:

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