1 Overview
CSE 305: Streams
Due: October 14, at 11:59 pm
The solution to this assignment has to be in Ocaml.
In this assignment you are asked to implement a few streams, functions over streams, and
functions to input from and output to file.
You are provided with the file streams.ml which you can use as a basis for your development.
In the file you are already given a type definition of a stream:
type ’a str = Cons of ’a * (’a stream) and
’a stream = unit -> ’a str
as well as the definition of basic combinators on streams whose types signatures are:
val head : ’a stream -> ’a val tail : ’a stream -> ’a stream val take : int -> ’a stream -> ’a list val map : (’a -> ’b) -> ’a stream -> ’b stream val zip : (’a -> ’b -> ’c) -> ’a stream -> ’b stream -> ’c stream val filter : ’a stream -> (’a -> bool) -> ’a stream val sieve : int stream -> int stream val nats : int -> int stream val primes : int stream val even : int -> bool val odd : int -> bool val fibs : int stream val ones : int stream val zeros : int stream
The previous functions can be helpful to implement your solution. You may also find helpful the combinators List.fold_left, List.filter, and List.rev from the standard library.
2
Tasks specifications
1. (6 points). The first task you need to solve is to define the stream of even numbers in increasing order. This value will have type int stream, remember that 0 is an even number.
2. (6 points ). As second task you need to define the stream of all the odd numbers in increasing order. This value will have type int stream.
1
- (6 points ). Define a function write_list_int: string -> int list -> unit. This func- tion writes a list of integers, provided as second argument, in a file, whose name is given as string in the first argument. The numbers have to be written one per line following the order left to right in the list. The function then returns unit.
- (6 points ). Define a function read_list_int_rev: string -> int list. This function takes the name of a file (which contains one integer per line) and returns a list of all the integers in reversed order. That is, if the file contains
12
3
then the function should return [3;2;1]. - (6 points). Define a function:
check_even_sum: string -> int -> (int list * int list * bool)
that takes as inputs the name of a file and a positive integer n and writes in the file the list of the first n even numbers using write_list_int. Let us call the previous list leven. The function then reads back from the same file using read_list_int_rev and returns the list of integers levenread. Finally, the function returns a tuple of three elements. The three elements are leven, levenread, and a boolean which is true if the sum of all the elements in leven is the same as the sum of all the elements in levenread and false otherwise.
- (6 points). Define a function
check_odd_rev: string -> int -> (int list * int list * bool)
that takes as inputs the name of a file and a positive integer n and writes in the file – whose name is specified as string by the first argument – the list of the first n odd numbers using write_list_int. Let us call the previous list lodd. The function then reads back from the same file using read_list_int_rev and returns the list of integers loddread. Finally, the function returns a tuple of three elements. The three elements are lodd, loddread, and a boolean which is true if the list lodd is the same as the list loddread in reversed order and false otherwise. While this task is similar to the previous one it is different.
- (6 points). Define a function
stream_zip: ’a stream -> ’b stream -> (’a * ’b) stream
that takes as inputs two streams of elements and returns the stream of pairs of elements. For instance, given in input the streams of natural numbers greater than 0, and the streams primes, then stream_zip should return a stream of pairs (i, pi) where pi is the i−th prime number, for i > 0. That is (1,2),(2,3),(3,5),(4,7),(5,11)….
- (6 points). Define a function incremental_map : (’a -> ’a ) -> a’ -> ’a stream, that given in input a function f, and an element a of type ’a produces the stream of elements a, (f a), (f (f a)), (f (f (f a))), (f (f (f (f a))))…. Forinstance,iffisthe function that maps x to x + 1. Then incremental_map f 0 should return the stream of ordered natural numbers.
- (6 points). Use incremental_map to define a stream of floats called exp_seq in which the i−th element is the (i − 1)-th element squared, and where the first element is 2. i.e. 2, 4, 16, 256, 65536 . . . This stream can be seen as the sequence of values of the mathematical sequence n → 22n, for n = 0,1,2…
2
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: 54. 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