Assignment 2

[Important: Do not use existing higher order functions, list comprehension, or any other advanced features of

Haskell not covered in class prior to release of the assignment. You must provide signature for every

function. Whenever meaningful, use type variables instead of types. Finally, ensure that the parameters

passed to the functions are of the correct types and are passed in the correct order.]

Part 1 Lambda Calculus and Currying

Total: 20 Points

[Note: Use “\” for the lambda character in your answers]

Problem 1 [10 Points]. Using the definitions of boolean constants and operators presented in class, show that

the following evaluates to false. Show all your steps for a perfect mark. Always evaluate the “outer”

applications first (i.e., use lazy evaluation), but continue to evaluate further until you obtain false.

and true (not true)

Problem 2 [5 + 5 Points]. Define the higher-order library function curry that converts a function on pairs into a

curried function, and, conversely, the function uncurry that converts a curried function with two arguments

into a function on pairs.

Part 2 Type System

Total: 40 Points

Problem 3 [40 Points]. Declare a data type MyFloat — for handling floating point numbers — where each

number is a (mantissa, exponent) pair of integers representing the floating point number mantissa x 10exponent

,

so that a decimal point is assumed to exist just to the left of the leftmost digit of mantissa. For example, (329,

23) would represent 0.329 x 1023

. Both the mantissa and the exponent can be positive or negative.

Carefully pick Haskell’s built-in type classes which this type should be an instance of. You should define

(and when possible overload) simple arithmetic and comparison operations on these floating numbers (at

least: *, /, +, -, negate (negation), <=, =, <, , ==). Also define functions whole and fraction to extract the

part of the represented number to the left of the decimal point (as an Int) and to the right of the decimal

number (as a standard Haskell floating point number), respectively. For example, for (329, 2), whole should

return 32, and fraction should return 0.9.

Part 3 Lists

Total 40 Points

Problem 4 [10 Points]. Write a polymorphic function, shuffle, which takes two lists l1 and l2 representing

decks of cards, and returns the perfectly shuffled contents of the lists. In other words, the returned list

contains the first element of l1, followed by the first element of l2, followed by the second element of l1, and

so on. If one of the lists ends before the other, the other list’s remaining elements are simply added to the

end.

Problem 5 [5 Points]. Write a polymorphic function, split, which takes as parameters a list and an Integer n,

indicating the splitting point. It splits the contents of the provided list into two lists, the first with the first n

elements of the list (in order), and the second with the remaining elements (again, in order). These two lists

are then returned as a pair.

Problem 6 [15 Points]. Write a function, nshuffle, which takes two integers c and n. It first generates two lists,

each of size c. One list contains c instances of the character ‘b’ (for black) and the other contains c instances

of the character ‘r’ (for red). Then, it carries out n number of perfect shuffles, splitting each shuffled list into

two equally sized lists before the next shuffle. For the shuffling and splitting, you must use functions shuffle

and split written for the previous two problems. The function returns the final outcome of the n shuffles in the

form of a single list. You may find it useful to define local functions for parts of this computation.

Problem 7 [10 Points]. Write a function, consecutive, which takes a list of characters, and returns an integer

indicating the largest number of consecutive identical characters in the list.

Submission:

Create a directory with your nsid as its name.

For Problem 1, put your answer in a text file named lambda.txt and place it in the directory.

For the remaining problems, place your functions in a Haskell source file called programs.hs. Create a

second text file programs.txt to show transcripts of your testing of the functions. Place both files in the

directory.

Once you have everything in your directory, create a zip file for the entire directory. If your nsid is <your_nsid

name the zip file <your_nsid.zip. When opened, it should create a directory called <your_nsid.

You may submit multiple times before the deadline, so you are advised not to wait till the last minute to submit

your assignment to avoid system slowdown. You are encouraged to submit completed parts of the

assignment early. Late submissions will not be accepted.

Sale!