Skip to content

Lab 3: Infinite List

Submission deadline: 2359, Friday, March 23, 2018.

Prerequisites

This lab assumes that students are

  • familiar with the concept of possibly infinite, lazily evaluated, list
  • familiar with the Stream operations map, filter, limit, reduce, count, takeWhile, toArray
  • familiar with creating, passing, storing, and invoking various lambda functions Predicate Supplier Consumer Function

Learning Objectives

After completing this lab, students should:

  • be comfortable with implementing a lazily evaluated list using lambdas.
  • be familiar with the concept of memoization in implementing a lazily evaluated list.

Setup

The skeleton code from Lab 3 is available on cs2030-i under the directory ~cs2030/lab3. There are two files, cs2030/lambda/InfiniteList.java, which you are asked to complete, and LabThree.java, which contains test code to test the behavior of InfiniteList.

Task

For Lab 3, you are asked to implement a bunch of methods for the class InfiniteList, a simple list that supports various lambda operations. See Grading section below for a (finite) list of methods to complete.

You are still required to

InfiniteList

A InfiniteList<T> is a generic list that can store elements of type T in order. Duplicates are allowed.

An InfiniteList is similar to Stream in Java, and so, you are NOT ALLOWED to solve this lab using Stream.

You have seen a simple version of InfiniteList in class on Monday. We are going to implement a better and more complicated version of that (so that code from Lecture 8 is not directly usable).

The main differences are:

  • Lab 3's version of InfiniteList is not always infinite. It can be truncated just like a Stream with limit and takeWhile operations. So methods such as findFirst need to consider the possibility of a finite list, including an empty list.

  • We need to be as lazy as possible and only generate the elements (i.e., invoke the Supplier's get() method) when necessary. Once we generate an element, we should not generate it again. So, we cache a copy of the value if it has been generated before. This logic has been written in the head() and tail() method for you.

Debugging Lazy Operations

In addition, to help with debugging what value has been cached, a toString method has been written and provided. It shows the value of an element if it has been cached, and ? if a value has not been generated. E.g., from jshell

1
2
3
4
5
6
7
8
jshell> InfiniteList<Integer> list = InfiniteList.iterate(5, x -> x + 5)
list ==> 5,?

jshell> list.takeWhile(x -> x < 40).count()
$22 ==> 7

jshell> list
list ==> 5,10,15,20,25,30,35,40,?

The Grader

We have also provided you with a class InfiniteListGrader, which is a subclass of InfiniteList. This grader class augments the Supplier for generate and the Function for iterate with a static counter, to count how many times these lambdas are invoked. To be lazy, your code should invoke them only when necessary, reusing existing values for head and tails whenever possible.

The counter can be retrieved with the numOfEvals() method and reset to 0 with the reset method. Example,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
jshell> InfiniteList<Integer> list = InfiniteListGrader.iterate(5, x -> x + 5)
list ==> 5,?

jshell> list.takeWhile(x -> x < 40).count()
$26 ==> 7

jshell> InfiniteListGrader.numOfEvals();
$27 ==> 7

jshell> InfiniteListGrader.reset();

jshell> list.limit(4).toArray()
$31 ==> Object[4] { 5, 10, 15, 20 }

jshell> InfiniteListGrader.numOfEvals();
$32 ==> 0

Note that the output of numOfEvals depends on the order of invocations, due to caching (aka memoization) of values. For instance, you will get a different output if you run limit(4).toArray() first before takeWhile(x -> x < 40).count() in the example above.

The cs2030.lambda Package

Both InfiniteList and InfiniteListGrader belong to the cs2030.lambda package. LabThree imports them for testing.

Grading

This lab contributes another 7 marks to your final grade. Correctly implementing each of the following items get you 1 marks:

  • generate, iterate, findFirst
  • reduce, toArray
  • map
  • limit
  • filter
  • takeWhile
  • count

You can get up to 1 mark deduction for violation of style. Note that "correct" here not only means it gives the correct output, but it should be lazy.

Submission

When you are ready to submit your lab, on cs2030-i, run the script 

1
~cs2030/submit3

which will copy the files matching cs2030/lambda/*.java (and nothing else) from your ~/lab3 directory on cs2030-i to an internal grading directory. We will test compile and test run with a tiny sample input to make sure that your submission is OK.

You can submit multiple times, but only the most recent submission will be graded.