CSE 305: Pattern Matching and Recursion
Due: October 3, at 11:59 pm
1 Overview
The solution to this assignment has to be in Ocaml. In this assignment you are asked to implement some basic functions with a specified behavior and type (or signature) working with a data type representing printable data which is defined as follow:
type printable = B of bool | I of int | C of char |
S of string | L of int list | P of printable * printable
This definition is also provided in the file printer.ml which you can use as a basis for your devel- opment.
A printable element can be a bool, an int, a char, a string, a list of int or a pair of printable elements (notice that the definition of printable is recursive). Here some examples of printable values:
ex1 = P (P (C ’z’, P (P (L [1; -5; 13], C ’c’), P (I 0, B true))),
S "Hello")
ex2 = P (P (B false, P (P (L [-21; 53; 12], S "c"), P (I 0, B false))), S "Hello") ex3 = P (P (C ’f’, P (P (L [15; -15; 213], S "c"), P (P (C ’t’, C ’t’), S "false"))),
S “Hello”)
We will use these examples in the sequel to illustrate the functions that you are required to imple- ment.
2 Function specifications
The first function you need to implement is count_chars whose behavior is to recursively traverses p and counts how many printable elements inside p are of the form C(c) for c:char. We can give to this function the following type:
count_chars: (p: printable) -> int.
For example, if we run count_chars on our examples we have:
count_chars ex1 = 2 count_chars ex2 = 0 count_chars ex3 = 3
The second function you need to implement is global_or whose behavior is to compute the logical or of all the booleans inside a printable value p. There are two “corner cases” that your solution needs to consider: 1) if there is exactly one Boolean in the printable p then global_or
1
should return this value as result, 2) if there is no Boolean in p then, since we cannot compute an or, global_or should return a value None asserting that no information is available. The type we want for tostring is then the following:
global_or: (p: printable) -> bool option.
For example, if we run global_or on our examples we have:
global_or ex1 = Some true global_or ex2 = Some false global_or ex3 = None
The third function you need to implement is f_on_int_list which should traverse a print- able p and apply a given function f to all the elements of each list in p. The type we want for f_on_int_list is the following:
f_on_int_list: (f: int->int) -> (p: printable) -> printable.
For example, if we run f_on_int_list on our examples with some auxiliary anonymous functions we have:
f_on_int_list (fun t-> t*t +1) ex1 =
P (P (C z, P (P (L [2; 26; 170], C c), P (I 0, B true))), S "Hello")
f_on_int_list (fun _-> 42) ex2 =
P (P (B false, P (P (L [42; 42; 42], S "c"), P (I 0, B false))),
S "Hello")
f_on_int_list (fun t-> 2*t) ex3 =
P (P (C f, P (P (L [30; -30; 426], S "c"), P (P (C t, C t), S "false"))),
S “Hello”)
You may find helpful here to use the function List.map.
The fourth function you need to implement is sum_all_ints which returns the sum of all the
integers in an input ptintable p. There is one “corner case” that your solution needs to consider: if there is no integer sum_all_ints should return a value None asserting that no information is available. The type we want for sum_all_ints is the following:
sum_all_ints: (p: printable) -> int option.
For example, if we run sum_all_ints on our examples we have:
sum_all_ints (P (C ’c’, S "42")) = None sum_all_ints (f_on_int_list (fun t-> 2*t) ex2) = Some 88 sum_all_ints (f_on_int_list (fun t-> t*t) ex3) = Some 45819
You may find helpful here to use the function List.fold_left to implement your solution.
The last function you need to implement is tostring which converts a printable element p into a string, following a pre-order traversal of the tree. That means that when you are converting to string a printable element of the form P(p1,p2) you need to concatenate the recursive calls as
(tostring p1)^(tostring p2). The type we want for tostring is the following: tostring: (p: printable) -> string.
For example, if we run tostring on our examples we have:
tostring ex1="z1-513c0trueHello" tostring ex2="false-215312c0falseHello" tostring ex3="f15-15213cttfalseHello"
2
You may find convenient in your solution to first define a function string_of_intlist converting a list of integers into a string which can then be used in the definition of tostring. The function string_of_intlist can be implemented using the functions List.fold_left and List.map that we saw in class. For this part of the assignment you may also find useful the standard library function Char.escaped which returns a string representing the given ASCII character (special characters are escaped following the lexical conventions of OCaml).
3 Submission Instructions
Late submissions will not be accepted. You can use Autolab to confirm your program adheres to the specification outlined. Only your last Autolab submission will be graded for you final grade. This means you can submit as many times as you want. If you have any questions please ask well before the due date.
3.1 Autolab account creation
An Autolab account has been already created for you. You can access Autolab at: https:// autograder.cse.buffalo.edu. If you already have an account for Autolab from a previous course or another course you are taking this semester you can log in normally and you should see CSE305 in your list of courses. If you have not used Autolab before you will need to go to: https: //autograder.cse.buffalo.edu/auth/users/sign_in and click on the Forgot your password? link. The following page will prompt you for your email address. Use your UB email address with your UBIT id as this is the email used to create your account for you. You will receive an email with instructions on how to reset your password and log into Autolab. It is important you verify your account is working well in advance of the turn in date.
3.2 Autolab submission instructions
When you log into Autolab and pick the CSE305 course you will see an assignment called Printer. Printer has only one part for OCaml. You will need to submit a solution to this part to have full credit for the assignment. The total of points for this assignment is: 50. On the Autolab page of Printer, set the number of inputs you want your code to be tested on. Click Submit and choose your source file. Your program should be an .ml file. You can submit as many times as you wish before the deadline.
3.3 Additional Resources
Additional Resources For information on how to run the various programming language compil- ers/interpreters:
• https://wiki.cse.buffalo.edu/services/content/ocaml
• https://caml.inria.fr/pub/docs/manual-ocaml/stdlib.html • https://caml.inria.fr/pub/docs/manual-ocaml/
You will find resources for these languages on the Piazza course web site, under the Re- sources page. You might also find the following page, listing available CSE systems, helpful too: https: //wiki.cse.buffalo.edu/services/content/student-systems.
3