CptS355 – Assignment 2 (Haskell)

Weight: Assignment 2 will count for 8% of your course grade.

This assignment provides experience in Haskell programming. Please compile and run your code on

command line using Haskell GHC compiler.

Turning in your assignment

The problem solution will consist of a sequence of function definitions and unit tests for those

functions. You will write all your functions in the attached HW2.hs file. You can edit this file and write

code using any source code editor (Notepad++, Sublime, Visual Studio Code, etc.). We recommend you

to use Visual Studio Code, since it has better support for Haskell.

To submit your assignment, please upload HW2.hs file to the Assignment2 (Haskell) DROPBOX on

Canvas (under Assignments).

The work you turn in is to be your own personal work. You may not copy another student’s code or

work together on writing code. You may not copy code from the web, or anything else that lets you

avoid solving the problems for yourself. At the top of the file in a comment, please include your name

and the names of the students with whom you discussed any of the problems in this homework. This

is an individual assignment and the final writing in the submitted file should be *solely yours*.

Important rules

• Unless directed otherwise, you must implement your functions using the basic built-in functions in

the Prelude library. (You are not allowed to import an additional library and use functions from

there.)

• If a problem asks for a non-recursive solution, then your function should make use of the higher

order functions we covered in class (map, foldr/foldl, or filter.) For those problems, your

main functions can’t be recursive. If needed, you may define non-recursive helper functions.

• Make sure that your function names match the function names specified in the assignment

specification. Also, make sure that your functions work with the given tests. However, the given

test inputs don’t cover all boundary cases. You should generate other test cases covering the

extremes of the input domain, e.g. maximum, minimum, just inside/outside boundaries, typical

values, and error values.

• Question 1(b) requires the solution to be tail recursive. Make sure that your function is tail

recursive otherwise you won’t earn points for this problem.

• You will call foldr/foldl, map, or filter in several problems. You can use the built-in

definitions of these functions.

• When auxiliary/helper functions are needed, make them local functions (inside a let..in or

where blocks). You will be deducted points if you don’t define the helper functions inside a

let..in or where block. If you are calling a helper function in more than one function, you can

define it in the main scope of your program, rather than redefining it in the let blocks of each calling

function.

• Be careful about the indentation. The major rule is “code which is part of some statement should

be indented further in than the beginning of that expression”. Also, “if a block has multiple

statements, all those statements should have the same indentation”. Refer to the following link for

more information: https://en.wikibooks.org/wiki/Haskell/Indentation

• Haskell comments : — line comment

{- multi line

comment-}.

Problems

1. remove_every, remove_every_tail_tail

(a) remove_every – 7%

Consider the following remove_every function. The function takes an integer n and a list lst and

removes the item after every n

th element in the list lst.

If n is greater than the length of the input list, no elements will be removed. If n is 0, all elements in the

list will be deleted. You may assume that n >=0.

The below remove_every function will give some type errors/run time exceptions when

compiled/run. Identify the problems and fix them. Explain the problems you identified/fixed in a

comment.

Examples:

> remove_every 3 “123a456b789c”

“123456789”

> remove_every 8 [1,2,3,4,5,6,7,8,100]

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

> remove_every 9 [1,2,3,4,5,6,7,8]

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

(b) remove_every_tail – 10%

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

remove_every_tail.

You may use the same test cases provided above to test your function.

remove_every n [] = []

remove_every n lst = remove_helper n lst n

where

remove_helper 0 (x:xs) k = (remove_helper k xs )

remove_helper n (x:xs) k = x:(remove_helper (n-1) xs)

2. get_outof_range and count_outof_range

(a) get_outof_range – 6%

Define a function get_outof_range which takes two values, v1 and v2, and a list “xs”, and returns

the values in xs which are less than v1 and greater than v2 (exclusive). Your function shouldn’t need

a recursion but should use a higher order function (map, foldr/foldl, or filter). You may need

to define additional helper function(s), which are also not recursive.

Examples:

> get_outof_range (-5) 5 [10,5,0,1,2,-5,-10]

[10,-10]

> get_outof_range 4 6 [1,2,3,4,5,6,7,8,9,10]

[1,2,3,7,8,9,10]

> get_outof_range ‘A’ ‘z’ “CptS-355”

“-355”

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: get_outof_range -5 5 [-10,-5,0,5,10] will give a type error, but

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

(b) count_outof_range – 10%

Using get_outof_range function you defined in part(a) and without using explicit recursion, define

a function count_outof_range which takes two integer values, v1 and v2, and a nested list “xs”,

and returns the total number of values in xs which are less than v1 and greater than v2 (exclusive).

Your function shouldn’t need a recursion but should use higher order function (map, foldr/foldl,

or filter). You may need to define additional helper function(s), which are also not recursive.

Examples:

> count_outof_range (-5) 5 [[10,5,0,1,2,-5,-10],[4,2,-1,3,-4,8,5,9,4,10],[-5,-

6,7,8]]

8

> count_outof_range ‘A’ ‘z’ [“Cpt S”,”-“,”355″,”:”,”HW2″]

7

> count_outof_range 1 1 [[4,1],[2,-1,3,-4],[8,0,1,5,9,4]]

10

3. find_routes – 10%

Assume the “routes” data we used in HW1.

routes = [

(“Lentil”, [“Chinook”, “Orchard”, “Valley”, “Emerald”,”Providence”, “Stadium”,

“Main”, “Arbor”, “Sunnyside”, “Fountain”, “Crestview”, “Wheatland”, “Walmart”,

“Bishop”, “Derby”, “Dilke”]),

(“Wheat”,[“Chinook”, “Orchard”, “Valley”, “Maple”,”Aspen”, “TerreView”, “Clay”,

“Dismores”, “Martin”, “Bishop”, “Walmart”, “PorchLight”, “Campus”]),

(“Silver”,[“TransferStation”, “PorchLight”, “Stadium”, “Bishop”,”Walmart”,

“Outlet”, “RockeyWay”,”Main”]),

(“Blue”,[“TransferStation”, “State”, “Larry”, “TerreView”,”Grand”, “TacoBell”,

“Chinook”, “Library”]),

(“Gray”,[“TransferStation”, “Wawawai”, “Main”, “Sunnyside”,”Crestview”,

“CityHall”, “Stadium”, “Colorado”]),

(“Coffee”,[“TransferStation”, “Grand”, “Main”, “Visitor”,”Stadium”, “Spark”,

“CUB”])

]

Rewrite the find_routes function in HW1 using higher order functions (map, foldr/foldl, or

filter) and without using recursion. Your helper functions should not be recursive as well, but they

can use higher order functions.

Remember that find_routes takes the list of bus routes and a stop name, and returns the list of the

bus routes which stop at the given bus stop. You can make use of elem function in your solution. The

order of the elements in the output can be arbitrary.

Examples:

> find_routes “Walmart” routes

[“Lentil”,”Wheat”,”Silver”]

> find_routes “Rosauers” routes

[]

> find_routes “Main” routes

[“Lentil”,”Silver”,”Gray”,”Coffee”]

4. add_lengths and add_nested_lengths

Consider the following Haskell datatype which represent the US customary length units:

data LengthUnit = INCH Int | FOOT Int | YARD Int

deriving (Show, Read, Eq)

(a) add_lengths – 6%

Define a Haskell function add_lengths that takes two LengthUnit values and calculates the sum

of those in INCH s. (Note that 1 foot = 12 inches and 1 yard = 36 inches)

Examples:

> add_lengths (INCH (-5)) (INCH 10)

(INCH 5)

> add_lengths (INCH 5) (FOOT 10)

(INCH 125)

> (add_lengths (YARD 1) (INCH 10)

(INCH 46)

(b) add_nested_lengths – 10%

Define a Haskell function add_nested_lengths that takes a nested list of LengthUnit values

and calculates the sum of those in INCH s. Your function shouldn’t need a recursion but should use

functions “map” and “foldr (or foldl)”. You may define additional helper functions which are

not recursive.

(Hint: The base for fold needs to be a LengthUnit value. )

Examples:

> add_nested_lengths [[INCH (-5),INCH 10], [YARD (-1), YARD 2,FOOT 2],

[INCH 5],[]]

(INCH 70)

> add_nested_lengths [[INCH 5,FOOT 10],[FOOT (-10),YARD 5],[YARD (-5),

INCH (-5)]]

(INCH 0)

> add_nested_lengths [[YARD 2, FOOT 1], [YARD 1, FOOT 2, INCH 10],[YARD 3]]

(INCH 262)

5. sum_tree and create_sumtree

In Haskell, a polymorphic binary tree type with data both at the leaves and interior nodes might be

represented as follows:

data Tree a = NULL | LEAF a | NODE a (Tree a) (Tree a)

deriving (Show, Read, Eq)

NULL value represent a missing child for a NODE.

(a) sum_tree – 8%

Write a function sum_tree that takes a tree of type Tree and calculates the sum of the values stored

in both the leaves and interior nodes.

For example:

sum_tree for the given tree will return 55 .

8

0

4 4

NULL 9

0

0 NULL

10 7

NULL 13

Examples:

> sum_tree (NODE 8 (NODE 0 (LEAF 4) (NODE 4 NULL (LEAF 9)))

(NODE 0 (NODE 0 (LEAF 10) (NODE 7 NULL (LEAF 13))) NULL))

55

> sum_tree (NODE 0 (NODE 10 (LEAF 4) NULL) (NODE (-10) (NODE (-3) NULL (NODE 10

NULL (LEAF (-3)))) (LEAF (-4))))

4

(b) create_sumtree – 10%

Write a function create_sumtree takes a Tree value and returns a Tree where the interior

nodes store the sum of the leaf and node values underneath them (including NODE’s own

values). See the example below.

Examples:

> sum_tree (NODE 8 (NODE 0 (LEAF 4) (NODE 4 NULL (LEAF 9)))

(NODE 0 (NODE 0 (LEAF 10) (NODE 7 NULL (LEAF 13))) NULL))

NODE 55 (NODE 17 (LEAF 4) (NODE 13 NULL (LEAF 9))) (NODE 30 (NODE 30 (LEAF

10) (NODE 20 NULL (LEAF 13))) NULL)

> sum_tree (NODE 0 (NODE 10 (LEAF 4) NULL) (NODE (-10) (NODE (-3) NULL (NODE 10

NULL (LEAF (-3)))) (LEAF (-4))))

NODE 4 (NODE 14 (LEAF 4) NULL) (NODE (-10) (NODE 4 NULL (NODE 7 NULL (LEAF (-3))))

(LEAF (-4)))

6. list_tree – 16%

A polymorphic tree type with nodes of arbitrary number of children might be represented as follows

(note that the leaves store a list and interior nodes store list of “ListTree”s):

data ListTree a = LEAFs [a] | NODEs [(ListTree a)]

deriving (Show, Read, Eq)

Write a function list_tree that takes a function (f), a base value (base), and a ListTree (t) and

combines the values in the lists of the leaf notes in tree t by applying function f. (The leaves of the

tree are scanned from left to right). The combined values from all leaves are further combined with

function f.

8

0

4 4

NULL 9

0

0 NULL

10 7

NULL 13

55

17

4 13

NULL 9

30

30 NULL

10 20

NULL 13

list_tree is invoked as:

list_tree f base t

Example:

Examples:

> list_tree (+) 0

(NODEs [ NODEs [ LEAFs [1,2,3],LEAFs [4,5], NODEs [LEAFs [6], LEAFs []] ],

NODEs [],

LEAFs [7,8],

NODEs [LEAFs [], LEAFs []]

])

36

> list_tree max 0

(NODEs [ NODEs [ LEAFs [1,2,3],LEAFs [4,5], NODEs [LEAFs [6], LEAFs []] ],

NODEs [],

LEAFs [7,8],

NODEs [LEAFs [], LEAFs []]

])

8

max is the built-in function that returns max of two values.

5. Tree examples – 4%

Create two trees of type Tree. The height of both trees should be at least 4. Test your functions

sum_tree, create_sumtree with those trees.

The trees you define should be different than those that are given. Make sure to change the shape of

the trees; just changing the values will not make your trees different.

Include your example trees at the end of your HW2.hs file – under the comment INCLUDE YOUR TREE

EXAMPLES HERE .

In this assignment you won’t submit any test files.

[7,8]

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

[6] [ ]

Assignment rules – 3%

Make sure that your assignment submission complies with the following. :

– The module name of your HW2.hs files should be HW2. Please don’t change the module name in

your submission file.

– The function names in your solutions should match the names in the assignment prompt. Running

the given tests will help you identify typos in function names.

– Make sure to remove all test data from the HW2.hs file, e.g. , tree examples provided in the

assignment prompt , the test files and the ‘routes‘ list for Problem-3.

– Make sure to define your helper functions inside a let..in or where block.

– Make sure that your solutions meet the specified requirements:

o Your solution for 1(b) should be tail-recursive.

o Your solutions for 2(a), 2(b), 3, and 4(b) shouldn’t need a recursion but should use

higher order function(s) map, foldr/foldl, or filter.

Testing your functions

The HW2SampleTests.zip file includes 10 .hs files where each one includes the HUnit tests for a

different HW 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 HW2 module (HW2.hs file) which will include

your implementations of the HW problems.

You will write your solutions to HW2.hs file. To test your solution for each HW problem run the

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

$ ghci

$ :l P2a_HW2tests.hs

# run

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

P3_HW2tests.hs, etc.

You don’t need to submit any tests for this assignment. However, you should still test your solutions

using additional input. Make sure to test your code for boundary cases.