## Description

Lab Problems

1. merge2, merge2Tail, and mergeN

(a) merge2

The function merge2 takes two lists, l1 and l2, and returns a merged list where the elements from l1

and l2 appear interchangeably. The resulting list should include the leftovers from the longer list and it

may include duplicates.

The type of merge2 should be compatible with merge2 :: [a] -> [a] -> [a].

Examples:

> merge2 [3,2,1,6,5,4] [1,2,3]

[3,1,2,2,1,3,6,5,4]

> merge2 “Ct 5” “pS35”

“CptS 355”

> merge2 [(1,2),(3,4)] [(5,6),(7,8),(9,10)]

[(1,2),(5,6),(3,4),(7,8),(9,10)]

> merge2 [1,2,3] []

[1,2,3]

(b) merge2Tail

Re-write the merge2 function from part (a) as a tail-recursive function. Name your function

merge2Tail.

The type of merge2Tail should be compatible with merge2Tail :: [a] -> [a] -> [a].

You can use reverse or revAppend in your solution. We defined revAppend in class.

(c) mergeN

Using merge2 function defined above and the foldl function, define mergeN which takes a list of

lists and returns a new list containing all the elements in sublists. The sublists should be merged left to

right, i.e., first two lists should be merged first and the merged list should further be merged with the

third list, etc. Provide an answer using foldl; without using explicit recursion.

The type of mergeN should be compatible with : mergeN:: [[a]] -> [a]

Examples:

> mergeN [“ABCDEF”,”abcd”,”123456789″,”+=?$”]

“A+1=a?2$B3b4C5c6D7d8E9F”

> mergeN [[3,4],[-3,-2,-1],[1,2,5,8,9],[10,20,30]]

[3,10,1,20,-3,30,2,4,5,-2,8,-1,9]

> mergeN [[],[],[1,2,3]]

[1,2,3]

2. count and histogram

(a) count

Define a function count which takes a value and a list as input and it count the number of occurrences

of the value in the input list. Your function should not need a recursion but should use a higher order

function (map, foldr/foldl, or filter). Your helper functions should not be recursive as well, but

they can use higher order functions. You may use the length function in your implementation.

The type of the count function should be compatible with count :: Eq a => a -> [a] -> Int

Examples:

> count [] [[],[1],[1,2],[]]

2

> count (-5) [1,2,3,4,5,6,7]

0

> count ‘i’ “incomprehensibilities”

5

(b) histogram

The function histogram creates a histogram for a given list. The histogram will be a list of tuples

(pairs) where the first element in each tuple is an item from the input list and the second element is the

number of occurrences of that item in the list. Your function shouldn’t need a recursion but should use

a higher order function (map, foldr/foldl, or filter). Your helper functions should not be

recursive as well, but they can use higher order functions. You may use the count function you defined

in part (a) and eliminateDuplicates function you defined in HW1.

The order of the tuples in the histogram can be arbitrary. The type of the function should be compatible

with histogram :: Eq a => [a] -> [(a, Int)]

Examples:

> histogram [[],[1],[1,2],[1],[],[]]

[([1,2],1),([1],2),([],3)]

> histogram “macadamia”

[(‘c’,1),(‘d’,1),(‘m’,2),(‘i’,1),(‘a’,4)]

> histogram (show 122333444455555)

[(‘1’,1),(‘2’,2),(‘3’,3),(‘4’,4),(‘5’,5)]

3. concatAll, concat2Either, and concat2Str

(a) concatAll

Function concatAll is given a nested list of strings and it returns the concatenation of all

strings in all sublists of the input list. Your function should not need a recursion but should use functions

“map” and “foldr”. You may define additional helper functions which are not recursive.

The type of the concatAll function should be:

concatAll :: [[String]] -> String

Examples:

> concatAll [[“enrolled”,” “,”in”,” “],[“CptS”,”-“,”355″],[” “,”and”,”

“],[“CptS”,”-“,”322”]]

“enrolled in CptS-355 and CptS-322”

> concatAll [[],[]]

“”

(b) concat2Either

Define the following Haskell datatype:

data AnEither = AString String | AnInt Int

deriving (Show, Read, Eq)

Define a Haskell function concat2Either that takes a nested list of AnEither values and it returns

an AString, which is the concatenation of all values in all sublists of the input list. The parameter of

the AnInt values should be converted to string and included in the concatenated string. You may use

the show function to convert an integer value to a string.

Your concat2Either function shouldn’t need a recursion but should use functions “map” and

“foldr”. You may define additional helper functions which are not recursive. The type of the

concat2Either function should be:

concat2Either:: [[AnEither]] -> AnEither

(Note: To implement concat2Either, change your concatAll function and your helper function in

order to handle AnEither values instead of strings.)

Examples:

> concat2Either [[AString “enrolled”, AString ” “, AString “in”, AString ” “],[AString

“CptS”, AString “-“, AnInt 355], [AString ” “, AString “and”, AString ” “], [AString

“CptS”, AString “-“, AnInt 322]]

AString “enrolled in CptS-355 and CptS-322”

> concat2Either [[AString “”, AnInt 0],[]]

AString “0”

> concat2Either []

AString “”

4. concat2Str

Re-define your concat2Either function so that it returns a concatenated string value instead of an

AString value. Similar to concat2Either, the parameter of the AnInt values should be converted

to string and included in the concatenated string.

Your concat2Str function shouldn’t need a recursion but should use functions “map” and

“foldr”. You may define additional helper functions which are not recursive. The type of the

concat2Str function should be:

concat2Str:: [[AnEither]] -> String

(Note: To implement concat2Str, change your concat2Either function and your helper function

in order to return a string value instead of an AnEither value.)

> concat2Str [[AString “enrolled”, AString ” “, AString “in”, AString ” “],[AString

“CptS”, AString “-“, AnInt 355], [AString ” “, AString “and”, AString ” “], [AString

“CptS”, AString “-“, AnInt 322]]

“enrolled in CptS-355 and CptS-322”

> concat2Str [[AString “”, AnInt 0],[]]

“0”

> concat2Str []

“”

evaluateTree, printInfix, createRTree

Consider the following Haskell type Op that defines the major arithmetic operations on integers.

data Op = Add | Sub | Mul | Pow

deriving (Show, Read, Eq)

The following function “evaluate” takes an Op value as argument and evaluates the operation on the

integer arguments x and y.

evaluate:: Op -> Int -> Int -> Int

evaluate Add x y = x+y

evaluate Sub x y = x-y

evaluate Mul x y = x*y

evaluate Pow x y = x^y

Now, we define an expression tree as a Haskell polymorphic binary tree type with data at the leaves and

Op operators at the interior nodes:

data ExprTree a = ELEAF a | ENODE Op (ExprTree a) (ExprTree a)

deriving (Show, Read, Eq)

5. evaluateTree

Write a function evaluateTree that takes a tree of type (ExprTree Int) as input and evaluates

the tree from bottom-up.

The type of the evaluateTree function should be evaluateTree :: ExprTree Int -> Int

For example:

> evaluateTree (ENODE Mul (ENODE Sub (ENODE Add (ELEAF 4) (ELEAF 5)) (ELEAF 6))

(ENODE Sub (ELEAF 10) (ELEAF 8)))

6

> evaluateTree (ENODE Add (ELEAF 10)

(ENODE Sub (ELEAF 50) (ENODE Mul (ELEAF 3) (ELEAF 10))))

30

> evaluateTree (ELEAF 4)

4

6. printInfix – 10%

Write a function printInfix that takes a tree of type (ExprTree a) as input and prints the

operands in the interior nodes and the values in the leaf nodes in “in-fix” order to a string. The

expressions lower in the tree are enclosed in parenthesis.

The type of the printInfix function should be:

printInfix:: Show a => ExprTree a -> String

For example:

> printInfix (ENODE Mul (ENODE Sub (ENODE Add (ELEAF 4) (ELEAF 5)) (ELEAF 6))

(ENODE Sub (ELEAF 10) (ELEAF 8)))

“(((4 `Add` 5) `Sub` 6) `Mul` (10 `Sub` 8))”

> printInfix (ENODE Add (ELEAF 10)

(ENODE Sub (ELEAF 50) (ENODE Mul (ELEAF 3) (ELEAF 10))))

“(10 `Add` (50 `Sub` (3 `Mul` 10)))”

> printInfix (ELEAF 4)

“4”

4 5

6 10 8

Mul

Add

Sub Sub

evaluateTree on the left tree returns 6.

4 5

6 10 8

Mul

Add

Sub Sub

printInfix on the left tree returns :

“(((4 `Add` 5) `Sub` 6) `Mul` (10 `Sub` 8))”

7. createRTree

Consider the following Haskell tree type.

data ResultTree a = RLEAF a | RNODE a (ResultTree a) (ResultTree a)

deriving (Show, Read, Eq)

Write a function createRTree that takes a tree of type (ExprTree Int) as input and creates a

tree of type (ResultTree Int). createRTree recursively evaluates each subtree in the input tree

and store the evaluated values in the corresponding nodes in the output ResultTree.

The type of the createRTree function should be:

createRTree :: ExprTree Int -> ResultTree Int

For example:

> createRTree (ENODE Mul (ENODE Sub (ENODE Add (ELEAF 4) (ELEAF 5)) (ELEAF 6))

(ENODE Sub (ELEAF 10) (ELEAF 8)))

RNODE 6 (RNODE 3 (RNODE 9 (RLEAF 4) (RLEAF 5)) (RLEAF 6)) (RNODE 2 (RLEAF 10) (RLEAF 8))

> createRTree (ENODE Add (ELEAF 10) (ENODE Sub (ELEAF 50) (ENODE Mul (ELEAF 3) (ELEAF 10))))

RNODE 30 (RLEAF 10) (RNODE 20 (RLEAF 50) (RNODE 30 (RLEAF 3) (RLEAF 10)))

> createRTree (ELEAF 4)

RLEAF 4

Testing your functions

The Lab2SampleTests.zip file includes 7 .hs files where each one includes the HUnit tests for a

different lab problem. The tests compare the actual output to the expected (correct) output and raise an

exception if they don’t match. The test files import the Lab2 module (Lab2.hs file) which will include

your implementations of the lab problems.

You will write your solutions to Lab2.hs file. To test your solution for the first lab problem run the

following commands on the command line window (i.e., terminal):

$ ghci

$ :l Q1_tests.hs

*Q1_tests> main

Repeat the above for other lab problems by changing the test file name, i.e. , Q2_tests.hs,

Q3_tests.hs, etc.

createRTree on the left tree returns :

4

6 10 8

Mul

Sub Sub

Add

5

[4,5,3,6,2,8,9,7,1

4 ]

6 10 8

6

3 2

9

5

Important note about negative integer arguments:

In Haskell, the -x, where x is a number, is a special form and it is a prefix (and unary) operator negating an integer

value. When you pass a negative number as argument function, you may need to enclose the negative number in

parenthesis to make sure that unary (-) is applied to the integer value before it is passed to the function.

For example: foo -5 5 [-10,-5,0,5,10] will give a type error, but

foo (-5) 5 [-10,-5,0,5,10] will work