Starting from:
$30
CSCE314-Assignment 1 Functional Programming in Haskell Solved
In this assignment, you will practice the basics of functional programming in Haskell. You
1. Read the problem descriptions and requirements carefully! There may be significantpenalties for not fulfilling the requirements.
2. Some problems ask you to explain the working of your function with the given input.Your explanation must be consistent with your definition of the function. Your work will be graded not only on the correctness of your answer, but also on the consistency and clarity with which you express it.
Below, the exercise problems are from the Haskell Textbook: “Programming in Haskell, 2nd Ed.” by Graham Hutton. Some problems are modified (with additional requirements) by the instructor. Please read textbook Chapters 1 thru 6 and the problem statements carefully. Keep the name and type of each function exactly the same as given in the problem statement and the skeleton code.
Problem 1. Put your full name, UIN, and acknowledgements of any help received in the head comment in your .hs file.
Problem 2. The n-th Lucas number `n is recursively defined as follows: `0 = 2 and `1 = 1 and `n = `n−1+`n−2 for n≥ 2. Write a recursive function lucas that computes the n-th Lucas number. lucas :: Int - Int
Problem 3.) Chapter 1, Exercise 4 (modified).
Study the definition of the function qsort given in the text carefully, and try it out with an integer list, for example, [3,2,3,1,4]. You will notice that it sorts a list of elements in an ascending order.
3.1 Write a recursive function qsort1 that sorts a list of elements in a descending order.
qsort1 :: Ord a = [a] - [a]
3.2 Write your answer for this question in a block comment following the definition of function qsort1. Suppose that qsort1 is invoked with the input [3,2,3,1,4]. How many times is qsort1 called recursively (i.e., without counting the first invocation of qsort1 [3,2,3,1,4])? Explain step-by-step, in particular, at each level of recursive call, what are the values of x, smaller, and larger? [Hint: Think using a binary tree structure.]
Problem 4. Chapter 5, Exercise 9 (modified).
The scalar product function should be able to take not only two lists of the same length n but also those of different lengths.
4.1 Using the list comprehension with the zip prelude function, write the scalar product function.
scalarproduct :: [Int] - [Int] - Int
4.2 Explain carefully step-by-step the working of your scalarproduct function when it is invoked as follows.
*Main scalarproduct [1,2,3] [4..]
Problem 5. Chapter 6, Exercise 7.
Like in the previous problem, the merge function should be able to take two sorted lists of different lengths as well as those of the same length.
merge :: Ord a = [a] - [a] - [a]
Problem 6. Chapter 6, Exercise 8.
Defining function halve is required (hint: use splitAt prelude function).
(8 points) msort :: Ord a = [a] - [a] (7 points) halve :: [a] - ([a], [a])
Problem 7. Write a recursive function isElem that returns True if a given value is an element of a list or False otherwise.
isElem :: Eq a = a - [a] - Bool
Sets are the most fundamental discrete structure on which all other discrete structures are built. In the following problem (and continuing in the next homework set), we are going to implement mathematical sets and their operations using Haskell lists.
A set is an unordered collection of elements (objects) without duplicates, whereas a list is an ordered collection of elements in which multiplicity of the same element is allowed. We define Set as a type synonym for lists as follows: type Set a = [a]
Even though the two types – Set a and [a] – are the same to the Haskell compiler, they communicate to the programmer that values of the former are sets and those of the latter are lists.
Problem 8. Write a recursive function that constructs a set from a list. Constructing a set from a list simply means removing all duplicate values. Use isElem from the previous problem in the definition of toSet.
toSet :: Eq a = [a] - Set a
Skeleton code and modes of running your code: The file hw1-skeleton.hs contains “stubs” for all the functions you are going to implement and placeholders for your explanations. The Haskell function bodies are initially undefined, a special Haskell value that has all possible types (thus, the skeleton file at least compiles).
In the skeleton file you find a test suite that test-evaluates the functions. Initially, all tests fail, until you provide correct implementation for the Haskell function. The tests are written using the HUnit library. Feel free to add more tests to the test suite.
The skeleton code can be loaded to the interpreter ( ghci hw1-skeleton.hs). In the interpreter mode, you can test individual functions one at a time while you are implementing them. Evaluating the function main (by main in the interpreter mode) runs all of the tests in the test suite.
Alternatively, you can compile the code and execute it in the terminal mode:
ghc hw1-skeleton.hs and then
./hw1-skeleton which has the same effect as when you do main in the interpreter mode.
[1] Version 7 is installed in the departmental servers (linux.cse.tamu.edu and compute.cse.tamu.edu), and version 8 is what you will get if you install the Haskell system in your computer.
1. Read the problem descriptions and requirements carefully! There may be significantpenalties for not fulfilling the requirements.
2. Some problems ask you to explain the working of your function with the given input.Your explanation must be consistent with your definition of the function. Your work will be graded not only on the correctness of your answer, but also on the consistency and clarity with which you express it.
Below, the exercise problems are from the Haskell Textbook: “Programming in Haskell, 2nd Ed.” by Graham Hutton. Some problems are modified (with additional requirements) by the instructor. Please read textbook Chapters 1 thru 6 and the problem statements carefully. Keep the name and type of each function exactly the same as given in the problem statement and the skeleton code.
Problem 1. Put your full name, UIN, and acknowledgements of any help received in the head comment in your .hs file.
Problem 2. The n-th Lucas number `n is recursively defined as follows: `0 = 2 and `1 = 1 and `n = `n−1+`n−2 for n≥ 2. Write a recursive function lucas that computes the n-th Lucas number. lucas :: Int - Int
Problem 3.) Chapter 1, Exercise 4 (modified).
Study the definition of the function qsort given in the text carefully, and try it out with an integer list, for example, [3,2,3,1,4]. You will notice that it sorts a list of elements in an ascending order.
3.1 Write a recursive function qsort1 that sorts a list of elements in a descending order.
qsort1 :: Ord a = [a] - [a]
3.2 Write your answer for this question in a block comment following the definition of function qsort1. Suppose that qsort1 is invoked with the input [3,2,3,1,4]. How many times is qsort1 called recursively (i.e., without counting the first invocation of qsort1 [3,2,3,1,4])? Explain step-by-step, in particular, at each level of recursive call, what are the values of x, smaller, and larger? [Hint: Think using a binary tree structure.]
Problem 4. Chapter 5, Exercise 9 (modified).
The scalar product function should be able to take not only two lists of the same length n but also those of different lengths.
4.1 Using the list comprehension with the zip prelude function, write the scalar product function.
scalarproduct :: [Int] - [Int] - Int
4.2 Explain carefully step-by-step the working of your scalarproduct function when it is invoked as follows.
*Main scalarproduct [1,2,3] [4..]
Problem 5. Chapter 6, Exercise 7.
Like in the previous problem, the merge function should be able to take two sorted lists of different lengths as well as those of the same length.
merge :: Ord a = [a] - [a] - [a]
Problem 6. Chapter 6, Exercise 8.
Defining function halve is required (hint: use splitAt prelude function).
(8 points) msort :: Ord a = [a] - [a] (7 points) halve :: [a] - ([a], [a])
Problem 7. Write a recursive function isElem that returns True if a given value is an element of a list or False otherwise.
isElem :: Eq a = a - [a] - Bool
Sets are the most fundamental discrete structure on which all other discrete structures are built. In the following problem (and continuing in the next homework set), we are going to implement mathematical sets and their operations using Haskell lists.
A set is an unordered collection of elements (objects) without duplicates, whereas a list is an ordered collection of elements in which multiplicity of the same element is allowed. We define Set as a type synonym for lists as follows: type Set a = [a]
Even though the two types – Set a and [a] – are the same to the Haskell compiler, they communicate to the programmer that values of the former are sets and those of the latter are lists.
Problem 8. Write a recursive function that constructs a set from a list. Constructing a set from a list simply means removing all duplicate values. Use isElem from the previous problem in the definition of toSet.
toSet :: Eq a = [a] - Set a
Skeleton code and modes of running your code: The file hw1-skeleton.hs contains “stubs” for all the functions you are going to implement and placeholders for your explanations. The Haskell function bodies are initially undefined, a special Haskell value that has all possible types (thus, the skeleton file at least compiles).
In the skeleton file you find a test suite that test-evaluates the functions. Initially, all tests fail, until you provide correct implementation for the Haskell function. The tests are written using the HUnit library. Feel free to add more tests to the test suite.
The skeleton code can be loaded to the interpreter ( ghci hw1-skeleton.hs). In the interpreter mode, you can test individual functions one at a time while you are implementing them. Evaluating the function main (by main in the interpreter mode) runs all of the tests in the test suite.
Alternatively, you can compile the code and execute it in the terminal mode:
ghc hw1-skeleton.hs and then
./hw1-skeleton which has the same effect as when you do main in the interpreter mode.
[1] Version 7 is installed in the departmental servers (linux.cse.tamu.edu and compute.cse.tamu.edu), and version 8 is what you will get if you install the Haskell system in your computer.
1 file (4.7KB)
