## Description

Programming Languages

Assignment 2

In this assignment, you will practice (i) list comprehension, (ii) functional

programming using higher-order functions, (iii) programmer defined data

types in Haskell, and (iv) representing programs as their abstract syntax

trees and evaluating them.

Below, you will find problem descriptions with specific requirements (for

example, “Using foldr, define . . . ” means that using the foldr function in

the definition is required). Read the descriptions and requirements carefully!

There may be significant penalties for not fulfilling the requirements. You

will earn total 120 points.

Note 1: This homework set is individual homework, not a team-based effort.

Discussion of the concept is encouraged, but actual write-up of the solutions

must be done individually.

Note 2: Submit electronically exactly one file, namely, yourLastName-yourFirstNamea2.hs, and nothing else, on eCampus.tamu.edu.

Note 3: Please make sure that the Haskell script (the .hs file) you submit

compiles without any error when compiled using the Glasgow Haskell Compiler (ghc), If your program does not compile, there is a chance that you

receive zero points for this assignment.

Note 4: Remember to put the head comment in your file, including your

name, UIN, and acknowledgements of any help received in doing this assignment. You will get points deducted if you do not put the head comment.

Keep the name and type of each function exactly as given.

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