CODEWITHSUNDEEP
haskelllambda-calculus
ezyman
ezyman

Reputation: 399

How to perform beta reduction on a lambda abstraction?

In Will Kurt's book on Haskell, there is an example on how to overwrite a variable x in Haskell using lambda abstraction (not to be tried at home!). Here is the example:

(\x -> (\x -> (\x -> x) 4) 3) 2

I can get the answer which is 4 using GHCi but I want to perform beta reduction using a pen and a paper step by step to internalise the whole mechanism, however I am stuck at the first beta reduction:

(\x -> (\x -> (\x -> x) 4) 3) 2 => (\x -> (\x -> 2) 4) 3)

Obviously the above reduction seems not to be correct.

Edit: In response to @molbdnilo, the content from Will Kurt's book is given below.

"At this point, it should be clear that lambda functions, all by themselves, can be immensely powerful. To drive this point home, you can also do something that Haskell won’t normally let you do: overwrite variables! For this example, you’re going to use a let expression instead of the raw lambda expression for readability. In functional programming, it rarely makes sense to overwrite a variable on purpose, but to show it can be done, the next listing shows a function overwrite that takes a variable x and then overwrites its value three time

Listing 3.2 The overwrite function

overwrite x = let x = 2
in
let x = 3
in
let x = 4
in
x

This, by itself, is a useless function, but it should remind you of the way to redefine variables in GHCi:

GHCi> let x = 2
GHCi> x
2
GHCi> let x = 3
GHCi> x
3

...

Quick check 3.3 Redefine overwrite by using only lambdas.

" The answer to the above quick check is that lambda in my question:

(\x -> (\x -> (\x -> x) 4) 3) 2

Upvotes: 1

Views: 102

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476493

The first issue are the variable names. The xs are not all the same. We can replace the variables with an equivalent expression:

(\x1 -> (\x2 -> (\x3 -> x3) 4) 3) 2

next we can evaluate the outer expression:

(\x2 -> (\x3 -> x3) 4) 3

and then the now outer expression:

(\x3 -> x3) 4

and thus finally:

4

so x1 are just "throw away" variables that are used to create a function, but they don't do anything with the result. In Haskell, one uses const :: a -> b -> a to construct a function that returns a value (can be a function) regardless what value we use for the parameter.

Upvotes: 5

Related Questions