Description
Traditional lambdanotation
Turn in answers to Part B, C and D
A lambda abstraction has the form
\ x. E
In syntax in Haskell
\ x > E
which denotes a function with formal argument x and with body E E is called \ term (or \ expression)
Functions do not have names
Functions have a single argument
Functions with one argument can be generalized to multiple args
The only thing a function can do is to apply it to an argument
Notation used
E F
to denote the application of function E to actual argument F There are only three kinds of expressions

::=

Variables
 E_{1} E_{2} Application
 \x. E Abstraction
Part A:
You need to do this part inorder to understand the rest of the assignment.
Examples using Haskell
\x > x : is an example of a lambda abstraction which x is a variable bound by lambda.

What is the type of (\x > x)?

What is the value of (verify in ghci).


(\x > x) 3 ?



(\x > x) (+) 5 3 ?



(\x > x) (+)?



What would be a descriptive name for the abstractions in 2.b?


What is the value of (verify in ghci).


(\x > x +x ) 3



What is the expression ? (E)



(\x > 3) 6 ?



What would be a descriptive name for this abstractions?

Example of using lambda expressions to represent numbers
We shows how to express integers as lambda abstractions. We define what integer 0 looks like and a function successor that is applied recursively k+1 times to produce the k‘s integer. Therefore each integer in lambda calculus is in fact a function. (Underline indicates what will be changed.) Notice there is NO recursion!
zero = \ s . \ z . z
successor = \ n. \s. \ z ( s (( n s ) z ) ).
one = \ s. \ z . ( s z)
two = \ s. \z . ( s (s z))
one ??=?? successor zero
Apply successor function to zero
Replace words with lambda terms
successor zero = \ n. \ s. \ z. ( s ( ( n s ) z ) ) (\ s . \ z . z)
=> \ n. \ s. \ z. ( s ( ( n s ) z ) ) (\ s’ . \ z . z)
=> \ s. \ z. ( s ( ( \ s’ . \ z . z) s) z)

n to be replaced by lambda term (\ s’ . \ z . z)
and rename zero’s s to s’.

The result is ( \ s’ . \ z . z) Now apply
\ s’ . \ z . z to s
=> \ s. \ z. ( s ( \z’ . z’) z) )
=> \ s. \ z. ( s z )

The result is ( \z . z). Rename z to z’
Now apply ( \z’ . z’) to z.
one’s representation
Lambda Calculus is a simple notations that can be use to compute.
— but what about recursion ???
——————————————————————————————————————
(Reminder) Properties of functions
A function f is a rule that takes an input value x and returns a value f (x) or f x
The inputs x belong to a set X (called the domain of f ).
The values y = f (x) belong to a set Y (called the range(codomain) of f ).
Referential transparency is the property that appling f to an object a will always result in the same object f (a).
onetoone (injective) function has the property if f ( a ) = f (b ) then a equals b.
fix point property of a value:
A function f whose domain and range overlap often have one or more common domainrange value a with the property f ( a ) = a. These values are called fixed points.
You should be aware that the domain and range can be themselves sets of functions.
Helpful resource at Haskell.org: Haskell/Fix and recursion
Meaning of recursion
WHAT DOES RECURSION MEAN?
You know what a recursive function looks like:
length x = if x == [] then 0 else 1 + length (tail x)
How do we write this as a lambda abstraction?
(\x > if x == [] then 0 else 1 + ???(tail x))
Part B: What do we do with the ??? ?
Type (Do NOT cut and paste) the following nonrecursive definition in a Haskell file and load into ghci:


hLen :: (Num u, Eq t) => ([t] > u) > [t] > u



hLen = (\f x > if x == [] then 0 else 1 + (f (tail x)))



myLength ls = if ls == [] then 0 else 1 + myLength (tail ls)


Look at hLen —



Is hLen recursive? Why or why not?





Is hLen a HOF (higher order function)? Why or why not?





What is the value of






hLen sum [4,5,6] ?







hLen head [4,5,6] ?



Does hLen have anything to do with sum or head?
2. What is the value of
3. What is the relationship between hLen and myLength?
Part C: Factorial
Add the following definition of factorial to your Haskell file and reload into ghci.


factorial :: Integral a => a > a



factorial n = if n ==0 then 1 else n * (factorial (n – 1))


Define hFact to be a lambda abstraction such that it takes a function as an argument, and returns another function, similar to hLen. Write this so that hFact factorial = factorial. What is the type of hFact? (Follow the model of hLen)

Apply hFact to ( ^ 2) — What is the value of hFact (^ 2) 4?

What is the value of hFact factorial 5? Is it the same value as factorial 5?
Part D: General definition
Here hFact factorial is factorial, i.e. the factorial function is the “smallest” fixed point of hFact
In general, to give meaning to the recursive function
f = (\ x. if (cond(x)) then val(x) else expr(f, x))
(which cannot be expressed in lambdanotation), we define
H_{f} =(\ F > \ x > if (cond(x)) then val(x) else expr(F, x))
Fix ( Haskell’s version of the fixedpoint combinator)
1. Add the following definition of factorial’ to your haskell file:
> factorial’ = hFact factorial’
Remember that if x = f x then x is the fix point of f so hFact factorial‘ equals factorial‘
What is the type of factorial’ ?

Now we can define our fix point operator ( Haskells equivalent Y combinator)


fix f = f (fix f )

a. What is the type of fix?
b. What is the difference between the code below?



fix f = f (fix f ) and





fix f = f fix f ?



Combining all we have done — What is the value of


factorial 6 (definition given in part C)



hFact factorial 6 ( you defined in part C #2 )



factorial’ 6 (definition given in part D #1)



fix hFact 6 (definition given in part D)

Hope these examples pique your curiosity.