Description
Problems
1. merge2, merge2Tail, and mergeN – 22%
(a) merge2 – 6%
The function merge2 takes two lists of integers, L1 and L2, each already in ascending order, and
returns a merged list that is also in ascending order. The resulting list should include the elements from
both lists and may include duplicates.
The type of merge2 should be int list -> int list -> int list.
Examples:
> merge2 [2,5,6,8,9] [1,3,4,5,7,8,10]
[1,2,3,4,5,5,6,7,8,8,9,10]
> merge2 [1,2] [0,10,12]
[0,1,2,10,12]
> merge2 [1,3,3,5,5] [~1,2,4]
[~1,1,2,3,3,4,5,5]
> merge2 [1,2,3] []
[1,2,3]
(b) merge2Tail – 10%
Re-write the merge2 function from part (a) as a tail-recursive function. Name your function
merge2Tail.
(Hint: In your bases case(s), use revAppend (which we defined in class) to add the reverse of the accumulated
merged list to the other list.)
The type of merge2Tail should be int list -> int list -> int list.
(c) mergeN – 6%
Using merge2 function defined above and the fold function, define mergeN which takes a list of lists,
each already in ascending order, and returns a new list containing all of the elements in sublists in
ascending order. Provide an answer using fold; without using explicit recursion.
The type of mergeN should be int list list -> int list.
Examples:
> mergeN [[1,2],[10,12],[2,5,6,8,9]]
[1,2,2,5,6,8,9,10,12]
> mergeN [[3,4],[~3,~2,~1],[1,2,5,8,9]]
[~3,~2,~1,1,2,3,4,5,8,9]
2. getInRange and countInRange – 18%
(a) getInRange – 6%
Define a function getInRange which takes two integer values, v1 and v2, and a list L, and returns
the values in L which are greater than v1 and less than v2 (exclusive). Your function shouldn’t need a
recursion but should use a higher order function (map, fold, or filter). You may need to define
additional helper function(s), which are also not recursive.
The type of the getInRange function should be:
int -> int -> int list -> int list
Examples:
> getInRange 3 10 [1,2,3,4,5,6,7,8,9,10,11]
[4,5,6,7,8,9]
> getInRange ~5 5 [~10,~5,0,5,10]
[0]
> getInRange ~1 1 [~2,2,3,4,5]
[]
(b) countInRange – 12%
Using getInRange function you defined in part(a) and without using explicit recursion, define a
function countInRange which takes two integer values, v1 and v2, and a nested list L, and returns
the total number of values in L which are greater than v1 and less than v2 (exclusive). Your function
shouldn’t need a recursion but should use higher order function (map, fold, or filter). You may
need to define additional helper function(s), which are also not recursive.
The type of the countInRange function should be:
int -> int -> int list list -> int
Examples:
> countInRange 3 10 [[1,2,3,4],[5,6,7,8,9],[10,11]]
6
> countInRange ~5 5 [[~10,~5,~4],[0,4,5],[],[10]]
3
> countInRange 1 5 [[1,5],[1],[5],[]]
0
3. addLengths and addAllLengths – 18%
(a) addLengths – 10%
Define the following ML datatype which represent the US customary length units :
datatype lengthUnit = INCH of int | FOOT of int | YARD of int
Define an ML function addLengths 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)
The type of the addLengths function should be:
lengthUnit -> lengthUnit -> lengthUnit
Examples:
> addLengths (FOOT 2) (INCH 5)
INCH 29
> addLengths (YARD 3) (INCH 3)
INCH 111
> addLengths (FOOT 3) (FOOT 5)
INCH 96
(b) addAllLengths – 8%
Now, define an ML function addAllLengths 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 “fold”. You may define additional helper functions which are not recursive.
The type of the addAllLengths function should be:
lengthUnit list list -> lengthUnit
(Hint: The base for fold needs to be a lengthUnit value. )
Examples:
> addAllLengths [[YARD 2, FOOT 1], [YARD 1, FOOT 2, INCH 10],[YARD 3]]
INCH 262
> addLengths (YARD 3) (INCH 3)
INCH 111
> addAllLengths [[FOOT 2], [FOOT 2, INCH 2],[]]
INCH 50
> addAllLengths []
INCH 0
4. sumTree and createSumTree – 22%
In SML, a polymorphic binary tree type with data both at the leaves and interior nodes might be
represented as follows:
datatype ‘a Tree = LEAF of ‘a | NODE of ‘a * (‘a Tree) * (‘a Tree)
(a) sumTree – 7%
Write a function sumTree that takes a tree of type int Tree and calculates the sum of the values
stored in the leaves only. The type of the sumTree function should be: int Tree -> int
Examples:
> val t1 = NODE (1,
NODE(2, NODE (3,LEAF 4, LEAF 5), LEAF 6),
NODE(7, LEAF 8, LEAF 9))
> sumTree t1
32
> val t2 = NODE (0,
NODE(0, LEAF 4, NODE (0,LEAF 8, LEAF 9)),
NODE(0, NODE(0,LEAF 10, NODE (0, LEAF 12, LEAF 13)), LEAF 7))
> sumTree t2
63
> sumTree (LEAF 3)
3
4 5
6 8 9
1
3
2 7
[4,5,3,6,2,8,9,7,1
]
sumTree will return : 32
(b) createSumTree – 15%
Write a function createSumTree takes an int Tree value and returns an int Tree where
the interior nodes store the sum of the leaf values underneath them. See the example below.
The type of the createSumTree function should be int Tree -> int Tree
val t3 = NODE (0, NODE(0, NODE (0,LEAF 4, LEAF 5), LEAF 6),
NODE(0, LEAF 8, LEAF 9))
> createSumTree t3
returns
NODE (32, NODE (15,NODE (9,LEAF 4,LEAF 5),LEAF 6),
NODE (17,LEAF 8,LEAF 9))
5. foldListTree – 20%
(16 %) A polymorphic tree type with nodes of arbitrary number of children might be represented as
follows (note that the leafs store list and interior nodes store list of “listTree”s):
datatype ‘a listTree = listLEAF of (‘a list) | listNODE of (‘a listTree list)
Write a function foldListTree 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).
foldListTree is invoked as:
foldListTree f base t
where f is the combining function of type ‘a ->’a ->’a.
The type of foldListTree should be:
(‘a -> ‘a -> ‘a) -> ‘a -> ‘a listTree -> ‘a
4 5
6 8 9
0
0
0 0 =>
4 5
6 8 9
32
9
15 17
Example:
(c) Testing your tree functions – 4%:
Create two tree values : one ‘a Tree and a ‘a listTree (‘a will be substituted by the type of the
values stored in the tree). The height of both threes trees should be at least 3. Test your functions
sumTree, createSumTree, foldListTree with those trees. The trees you define should be
different than those that are given. You don’t need to write test functions for sumTree,
createSumTree, and foldListTree.
SML of NJ doesn’t display the full content of a tree value. To be able to display the full depth tree, you
need to increase the print depth parameter. In the beginning of your file, include the following (you may
also run this on the command line):
Control.Print.printDepth := 100;
Here is some additional test data for foldListTree.
> val L1 = listLEAF [“School”,”-“,”of”,”-“,”Electrical”]
> val L2 = listLEAF [“-“,”Engineering”,”-“]
> val L3 = listLEAF [“and”,”-“,”Computer”,”-“]
> val L4 = listLEAF [“Science”]
> val L5 = listLEAF [“-WSU”]
> val N1 = listNODE [L1,L2]
> val N2 = listNODE [N1,L3]
> val t5 = listNODE [N2,L4,L5]
> fun concat a b = a^b
> foldListTree concat “” t5 (* “” is empty string*)
“School-of-Electrical-Engineering-and-Computer-Science-WSU”
[7,8]
[1,2,3] [4,5] [ ] [ ]
[6] [ ]
val t4 = listNODE(
[ listNODE ([ listLEAF [1,2,3],listLEAF [4,5],listNODE([listLEAF [6], listLEAF []]) ]),
listNODE([]),
listLEAF [7,8],
listNODE([listLEAF [], listLEAF []]) ])
> foldListTree add 0 t4
36
Testing your functions
For each problem (except sumTree, createSumTree, foldListTree), write a test function that
compares the actual output with the expected (correct) output. Below is an example test function for
addAllLengths:
fun addAllLengthsTest () =
let
val addAllLengthsT1 = ((addAllLengths [[YARD 2,FOOT 1],[YARD 1,FOOT 2,INCH 10],[YARD 3]])=(INCH 262))
val addAllLengthsT2 = ((addLengths (YARD 3) (INCH 3)) = (INCH 111))
val addAllLengthsT3 = ((addAllLengths [[FOOT 2], [FOOT 2, INCH 2],[]]) = (INCH 50))
in
print (“addAllLengths:——————– \n” ^
” test1: ” ^ Bool.toString(addAllLengthsT1) ^ “\n” ^
” test2: ” ^ Bool.toString(addAllLengthsT2) ^ “\n” ^
” test4: ” ^ Bool.toString(addAllLengthsT3) ^ “\n”)
end
val _ = addAllLengthsTest()
Make sure to test your functions for at least 2 additional test inputs (in addition to the provided
examples).
Hints about using files containing ML code
In order to load files into the ML interactive system you have to use the function named use.
The function use has the following syntax assuming that your code is in a file in the current directory
named HW2.sml: You would see something like this in the output:
> use “HW2.sml”;
[opening file “HW2.sml”]
…list of functions and types defined in your file
[closing file “HW2.sml”]
> val it = () : unit
The effect of use is as if you had typed the content of the file into the system, so
each val and fun declaration results in a line of output giving its type.
If the file is not located in the current working directory you should specify the full or relative path-name
for the file. For example in Windows for loading a file present in the users directory in the C drive you
would type the following at the prompt. Note the need to use double backslashes to represent a single
backslash.
– use “c:\\users\\example.sml”;
Alternatively you can change your current working directory to that having your files before invoking the
ML interactive system.
You can also load multiple files into the interactive system by using the following syntax
– use “file1”; use “file2”;…; use “filen”;
How to quit the ML environment
Control-Z followed by a newline in Windows or Control-D in Linux will quit the interactive session.
