haskell Assignment 5 Solution

$30.00 $24.90

Description

Traditional lambda-notation

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

  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.

Examples using Haskell

\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.

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

        1. hLen head [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

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

  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)

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

  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.