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)
20
is the input of g
which yields k (h 20)
h 20
gives 20 + 1
= 21
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?
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
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With