\$30.00 \$24.90

Category:

## Description

Turn in answers to Part B, C and D

A lambda abstraction has the form

\ x. E

\ 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

1. ::=

1. Variables

| E1 E2 Application

| \x. E Abstraction

Part A:

You need to do this part inorder to understand the rest of the assignment.

\x -> x : is an example of a lambda abstraction which x is a variable bound by lambda.

1. What is the type of (\x -> x)?

1. What is the value of (verify in ghci).

1. (\x -> x) 3 ?

1. (\x -> x) (+) 5 3 ?

1. (\x -> x) (+)?

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

1. What is the value of (verify in ghci).

1. (\x -> x +x ) 3

1. What is the expression ? (E)

1. What is the value of (verify in ghci).

1. (\x -> 3) 6 ?

1. 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)

1. n to be replaced by lambda term (\ s’ . \ z . z)

and rename zero’s s to s’.

1. The result is ( \ s’ . \ z . z) Now apply

\ s’ . \ z . z to s

=> \ s. \ z. ( s ( \z’ . z’) z) )

=> \ s. \ z. ( s z )

1. 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(co-domain) of f ).

Referential transparency is the property that appling f to an object a will always result in the same object f (a).

one-to-one (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 domain-range 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.

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 non-recursive 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)

1. Look at hLen —

1. Is hLen recursive? Why or why not?

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

1. What is the value of

1. hLen sum [4,5,6] ?

Does hLen have anything to do with sum or head?

2. What is the value of

hLen myLength [4,5,6] ?

3. What is the relationship between hLen and myLength?

Part C: Factorial

• factorial :: Integral a => a -> a

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

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)

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

1. 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 lambda-notation), we define

Hf =(\ F -> \ x -> if (cond(x)) then val(x) else expr(F, x))

Fix ( Haskell’s version of the fixed-point combinator)

> 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’ ?

1. 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 ?

1. Combining all we have done — What is the value of

1. factorial 6 (definition given in part C)

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

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

1. fix hFact 6 (definition given in part D)

Hope these examples pique your curiosity.