Description
Part 1. List comprehensions/Higher Order Function
Problem 1. (10 points) Write a function that will delete leading white
space from a string.
cutWhitespace [” x”,”y”,” z”] ans: [”x”,”y”,”z”]
You are allowed to use any higher order function/List Comprehension(if you
want to use) to solve this problem.
1
Problem 2. (10 points) Write a function that will take two list of lists, and
multiply one with another. multList [[1,1,1],[3,4,6],[1,2,3]] [[3,2,2],[3,4,5],[5,4,3]]
ans: [[3,2,2],[9,16,30],[5,8,9]]
You are allowed to use any higher order function/List Comprehension(if you
want to use) to solve this problem.
You can use your own test case for Part 1(problem 1 and 2).
Part 2. Recursive functions, higher order functions
Problem 3. (8 points)
1. (8 points) Define a recursive function merge that merges two sorted
lists so that the resulting list is also sorted.
merge :: Ord a => [a] -> [a] -> [a]
For example: >merge [2,5,6] [1,3,4] ans: [1,2,3,4,5,6]
Note: your definition should not use other functions on sorted lists
such as insert or isort, but should be defined using explicit recursion.
2. (8 points) Using merge, define a function
msort :: Ord a => [a] -> [a]
that implements merge sort, in which the empty list and singleton lists
are already sorted, and any other list is sorted by merging together the
two lists that result from sorting the two halves of the list separately.
Hint: First define a function
halve :: [a] -> ([a],[a])
Problem 4. (5 points) Using foldr, define a function that multiplies all
elements of a list. Multiplying the empty list should return 1.
multiply :: [Int] -> Int
Problem 5. (5points) Using foldl, define a function that concatenates all
strings that are elements of a list.
concatenate :: [String] -> String
Problem 6. (10 points) Using map, filter, and . (function composition
operator), define a function that examines a list of strings, keeping only those
whose length is odd, converts them to upper case letters, and concatenates
the results to produce a single string.
concatenateAndUpcaseOddLengthStrings :: [String] -> String
You need to import Data.Char in order to use the toUpper function (see
the skeleton code).
2
Part 3: Data types, type classes
Consider the following data type.
data Tree a b = Branch b (Tree a b) (Tree a b)
| Leaf a
Problem 7. (10 points) Implement the two functions that traverse the tree
in the given order collecting the values from the tree nodes into a list:
preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
inorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
Notice that the data type Tree can store different types of values in the
leaves than on the branching nodes. Thus, each of these functions takes two
functions as arguments: The first function maps the values stored in the
leaves to some common type c, and the second function maps the values
stored in the branching nodes to type c, thus, resulting in a list of type [c].
Part 4: A tiny language
Let E (for expression) be a tiny programming language that supports the
declaration of arithmetic expressions involving only addition and multiplication, and equality comparisons on integers. Here is an example program
in E:
1 + 9 == 5 * ( 1 + 1 )
When evaluated, this program should evaluate to the truth value true.
In this exercise, we will not write E programs as strings, but as values of a
Haskell data type E, that can represent E programs as their abstract syntax
trees (ASTs). Given the following data type E,
data E = IntLit Int
| BoolLit Bool
| Plus E E — for addition
| Mult E E — for multiplication
| Equals E E
deriving (Eq, Show)
The above example program is represented as its AST:
program = Equals
(Plus (IntLit 1) (IntLit 9))
(Mult
(IntLit 5)
(Plus (IntLit 1) (IntLit 1)))
Problem 8. (20 points) Define an evaluator for the language E. Its name
and type should be
eval :: E -> E
3
The result of eval should not contain any operations or comparisons, just
a value constructed either with IntLit or BoolLit constructors. The result
of the example program above should be BoolLit True.
Note that E allows nonsensical programs, such as Plus (BoolLit True)
(IntLit 1). For such programs, the evaluator can abort.
4
