REVISED: Wednesday, January 24, 2024
Haskell Lambda Calculus Examples.
I. HASKELL LAMBDA CALCULUS REVIEW
A. LAMBDA CALCULUS λ AND . VERSUS HASKELL \ AND ->
For those of you who might have forgotten, rewriting "Lambda Calculus" anonymous function equations into Haskell only requires giving the λ equation a function name; replacing the λ with a backslash \, pronounced "lambda", which resembles the Greek λ without the hook; and the . with an arrow ->. The backslash binds the variables after it in the expression that follows the ->.
Lambda Calculus anonymous functions are used in Haskell to create short, concise functions that can be passed as parameters to other functions. They are also used to create closures, which are functions that can access variables from the surrounding scope.
To create a Lambda Calculus anonymous function in Haskell, you use the \ symbol followed by the names of the variables that the function will take as parameters, followed by a -> symbol, followed by the body of the function. For example, the following code creates a function that takes an integer as input and returns its square:
f = \x -> x * x
This function can then be called like any other function:
result = f 5
The result of this expression will be 25.
Lambda Calculus anonymous functions can also be used to create closures. A closure is a function that can access variables from the surrounding scope. To create a closure, you simply create a Lambda Calculus anonymous function and then assign it to a variable. For example, the following code creates a closure that stores the value of the variable x:
x = 10
f = \ -> x + 1
The function f can now access the value of the variable x, even though x was declared outside of the function's body.
Lambda Calculus anonymous functions are a powerful tool that can be used to create short, concise, and expressive code in Haskell. They are a fundamental part of the Haskell language and are used in many different ways.
1st Review Example
(λx.x*x)3
Prelude> let z1 = (\x -> x*x) 3 -- Formal x actual 3.
z1 :: Num a => a
Prelude>
Call the function z1 as follows:
Prelude> z1
9
it :: Num a => a
Prelude>
2nd Review Example
(λxλy.2*x+y*y)7 11
Prelude> let z2 = (\x y -> 2*x + y*y) 7 11 -- Formal x y actual 7 11.
z2 :: Num a => a
Prelude>
Call the function z2 as follows:
Prelude> z2
135
it :: Num a => a
Prelude>
3rd Review Example
(λxλy.12*x+y*y*y)6 6
Prelude> let z3 = (\x y -> 12*x + y*y*y) 6 6 -- Formal x y actual 6 6.
z3 :: Num a => a
Prelude>
Call the function z3 as follows:
Prelude> z3
288
it :: Num a => a
Prelude>
B. HASKELL FUNCTION FORMAL PARAMETERS AND ACTUAL PARAMETERS
A defined parameter is a formal parameter. In the definition of fB1 x below the first occurrence of x is the defined parameter x, it is the formal parameter of x.
An applied parameter is an actual parameter. Prelude> fB1 5 shows 5 as the actual parameter of x.
You define a function once; however, it can be applied many times.
"Copy Paste" the following fB1 function into your text editor and "File, Save As" fB1.hs in your working directory:
fB1 :: Num a => a -> a
fB1 x = g (x + 3)
whereg y = (x + y * y)
Load the function fB1 into GHCi as follows:
Prelude> :load fB1
[1 of 1] Compiling Main ( fB1.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Call the function fB1 as follows:
Prelude> fB1 5
69
it :: Num a => a
Prelude>
As shown above we did a lot of work to call the function fB1. Instead of all that work we could have done the following:
Prelude> let fB1 x = g (x + 3) where g y = (x + y * y)
fB1 :: Num a => a -> a
Prelude>
Call the function fB1 as follows:
Prelude> fB1 5
69
it :: Num a => a
Prelude>
Prelude>
Call the function fB1 as follows:
Prelude> fB1 5
69
it :: Num a => a
Prelude>
Prelude> :type fB1
fB1 :: Num a => a -> a
Prelude>
Which is the same as performing all of the following steps:
Step 1 fB1 5 = g (5 + 3) where g y = (5 + y * y) -- Replace formal x with actual 5.
Step 2 fB1 5 = g (8) where g 8 = (5 + 8 * 8) -- Compute and replace y.
Step 3 fB1 5 = g (8) where g 8 = (5 + 64)
Step 4 fB1 5 = g (8) where g 8 = (69)
C. SHADOWING
When you have an outer definition and an inner definition Haskell always picks the inner nested definition. This is called shadowing.
"Copy Past" the following function fC1 into your text editor and "File, Save As" fC1.hs in your working directory:
fC1 :: Num a => a -> a
fC1 x = fC1 (x+1)
where
fC1 y = x+y*y
Load the function fC1 into GHCi as follows:
Prelude> :load fC1
[1 of 1] Compiling Main ( fC1.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Call the function fC1 as follows:
Prelude> fC1 2
Call the function fC1 as follows:
Prelude> fC1 2
11
it :: Num a => a
Prelude>
Prelude>
Prelude> :type fC1
fC1 :: Num a => a -> a
Prelude>
In general the body of a function has to be a single expression which is very often made up of smaller expressions.
Prelude> let z = (\x -> \y -> x + y) 3 4
z :: Num a => a
Prelude>
Call the function z as follows:
Prelude> z
7
it :: Num a => a
Prelude>
(\x -> \y -> x + y) 3 4
=
((\x -> \y -> x + y) 3) 4
=
(\y -> 3 + y) 4
=
3 + 4
=
7
E. EVALUATING LAMBDA EXPRESSIONS
The general rule for evaluating lambda expressions is
(\x -> e) d
=
let x = d in e
This is sometimes called the β rule, or beta rule.
F. FUNCTION BINDING
A function binding can be written using an application on the left or a lambda expression on the right.
(M where f x = N)
=
(M where f = λx.N)
G. VARIABLE BINDING
A variable binding can be rewritten using a lambda expression and an application.
(N where x = M) -- = is read "is".
=
(λx.N)M -- Formal is x and actual is M.
H. LAMBDA BINDING EXAMPLES
The scope of a bound variable in a lambda expression is the lambda expression.
1st Example
"Copy Paste" the following function fH1 into your text editor and "File, Save As" fH1.hs in your working directory:
fH1 :: Num a => a -> a
fH1 x = x + y * y
where
y = x+ 1
Load the function fH1 into GHCi as follows:
Prelude> :load fH1
[1 of 1] Compiling Main ( fH1.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Call the function fH1 as follows:
Prelude> fH1 2
11
it :: Num a => a
Prelude>
Prelude> :type fH1
fH1 :: Num a => a -> a
Prelude>
2nd Example
"Copy Paste" the following function fH2 into you text editor and "File, Save As" fH2.hs in your working directory:
fH2 :: Integer -> Integer
fH2 = \x -> ((\y -> x + y * y) (x + 1))
Prelude> :load fH2
[1 of 1] Compiling Main ( fH2.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Call the function fH2 as follows:
Prelude> fH2 2
11
it :: Integer
Prelude>
Prelude> :type fH2
fH2 :: Integer -> Integer
Prelude>
Prelude> let fH2 = \x -> ((\y -> x + y * y) (x + 1))
Prelude>
Prelude> fH2 2
11
Prelude>
I. HASKELL SECTIONING OF AN INFIX BINARY OPERATOR
Parentheses () are placed around an infix binary operator to create a section. In a section one of the arguments of an operator is often included along with the binary operator. Sectioning is used when you do not want to write a lambda expression.
λ CALCULUS SECTION SHORTHAND
(> 0) is shorthand for (\x -> x > 0)
(2 *) is shorthand for (\x -> 2 * x)
(+ 1) is shorthand for (\x -> x + 1)
(2 ^) is shorthand for (\x -> 2 ^ x)
(^ 2) is shorthand for (\x -> x ^ 2)
(-1) is not a section but the number -1.
Boolean sections are written as ( op e ) or ( e op ), where op is a binary operator and e is an expression. Binary operators include >, >=, <, <=, /=, and == which produce a result of True or False.
(op e) = \ x -> x op e
(e op) = \ x -> e op x
Prelude> let f x = (> 0) x
Prelude>
Prelude> f 1
True
Prelude>
Prelude> f 0
False
Prelude>
Prelude> f (-1)
False
Prelude>
2. INFIX OPERATOR SECTION
(2 *) left section is shorthand for (\x -> 2 * x)
Prelude> let f x = (2 *) x
Prelude>
Prelude> f 1
2
Prelude>
Prelude> f 0
0
Prelude>
Prelude> f (-1)
-2
Prelude>
(+ 1) right section is shorthand for (\x -> x + 1)
Prelude> let f x = (+ 1) x
Prelude>
Prelude> f 1
2
Prelude>
Prelude> f 0
1
Prelude>
Prelude> f (-1)
0
Prelude>
(2 ^) left section is shorthand for (\x -> 2 ^ x)
Prelude> let f x = (2 ^) x
Prelude>
Prelude> f 1
2
Prelude>
Prelude> f 0
1
Prelude>
Prelude> f (-1)
*** Exception: Negative exponent
Prelude>
(^ 2) right section is shorthand for (\x -> x ^ 2)
Prelude> let f x = (^ 2) x
Prelude>
Prelude> f 1
1
Prelude>
Prelude> f 0
0
Prelude>
Prelude> f (-1)
1
Prelude>
II. CONCLUSION
This tutorial is a refresher course of rewriting "Lambda Calculus" equations into Haskell.
III. REFERENCES
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.
