CS2030S Lab 7: Memo List Solution

Prerequisite
• Caught up to Unit 32 of Lecture Notes
Important Concepts Tested
• Memo: Compute only when needed & do not repeat yourself
• PECS: Make your method signature as flexible as possible
• JavaDoc: Documenting your code and generating the documentation
Files
You are given the following implementation for your Lab 7:
fp . Action
Immutator
fp . Constant
fp . Combiner
fp . Actionable
fp . Immutato rable
fp . Actually
fp . Memo
The files Test 1 . java , Test2 . java , etc., as well as CS2Ø3ØSTest . java , are provided for testing. You can edit them to add your test cases, but they will not be submitted.
You are given a badly implemented MemoList (which is just EagerList copied into a new class). Further note that the Eager-List is different from our lecture note EagerList . This current EagerList is simply a wrapper for Java List . The EagerList and InfiniteList in lecture note will form the basis for Lab 8.
Furthermore, as a checkpoint in case you could not complete Actually and Memo on time or you are still facing many errors in its implementation, we provide an implementation of Actually and Memo . These implementations will not satisfy many of the requirements for Lab 5 and 6.
Otherwise, your submission will not work on CodeCrunch and you will get 0 mark for this lab.
Additionally, from here onwards, you will get 0 mark for your lab if you are using the unwrap method inside Actually . Our implementation of Actually no longer has unwrap .
IMPORTANT!
1. If you are using your own implementation of Memo , you MUST include the implementation of the Lazy class inside the file Memo . java . In other words, your
Memo. java must include two classes: Lazy and Memo .
2. You are NOT allowed to use unwrap method from Actually .
Preliminary
Actually
The class is simplified by not using inner[nested class. This is achieved by simply using a convention:
• If err is not null , then it is a Failure and we should not use the value of val .
• If err is null , then it is a Success and we can use the value of val including when val is null .
We no longer use a monospace font Failure and Success as they are no longer a class.
Another simplification is that we just have added a notion of a "common error" that can be created using the static method err( ) that takes in no argument. This common error can be used to indicate the most general kind of error you can think of. We also modified the equals method such that all Failure (i.e., the case when err is not null ) are considered to be the equal to each other.
Furthermore, note that we added a method check that takes in an Immutator<B001ean, super T> . This can be used to convert a Success to a Failure when the immutator predicate is not satisfied. Otherwise, this method returns itself.
Lastly, we simplify the toString() method to simply print when we are having a Failure. This is just a simplification as we no longer need to know the error inside.
MemO
The class Memo is simplified by not inheriting from Lazy . In fact, we remove Lazy completely and merge the field Constant<? extends T> into Memo . We will be using the following convention:
• If com is null , then we have evaluated the value and we can use the value of val including when val actually stores null .
• If com is not null , then we have not evaluated the value and we cannot use the value of val unless we evaluate it first using the private method eval .
The private method eval is used to force an evaluation of com into the value val . This will then set the value of com to null to prevent another evaluation as we have now memoized the value produced into val .
Memo List
The Memo class can be used to build a lazy-evaluated-and-memoized list.
Consider the class EagerList below. Given n , the size of the list, seed , the initial value, and f , an operation, we can generate an EagerList as [seed, f (seed) , f (f (seed)) , f(f(f(seed) ) ) , ] , up to n elements.
We can then use the method get(i) to find the i-th element in this list, or index0f(obj ) to find the index of obj in the list. (Hint: for index0f to work properly, you need to provide equals method in Memo where two Memo are equal if the elements are of the same type and equal based on their respective equals method.)
class EagerList<T> {
2 private List<T> list
3 private Eager List(List<T> list
4 this. list - list
5
6
7 public static < T> EagerList<T> generate(int n, T seed, Immutator<T,
8
9 EagerList<T> eagerList new EagerList<>(new ArrayList<>( ) ) ; T curr seed
11 for (int i
12 eagerList . list . add(curr) ;
13 curr f. invoke(curr) ;
14
15 return eager List
16
17
18 public T get (int i) {
19 return this . list. get (i) ;
28
21
22 public int indexOf(T v) { 23 return this . list. index0f(v) •
24
25
26 @0verride
27 public String toString( ) { 28 return this . list .toString( ) ;
29
But suppose f ( ) is an expensive computation, and we ended up just needing to get(k) where k is much smaller than N , then, we would have wasted our time computing all the remaining elements in the list! Similarly, if the obj that we want to find using index0f is near the beginning of the list, there is no need to compute the remaining elements of the list.
We want to change this EagerList into a MemoList that make use of the Memo class such that get() and index0f() causes evaluation of f ( ) only as many times as necessary. The first step is already done for you, we have made a copy of Eager-List into MemoList but it has not used Memo yet. Change this implementation to use Memo . (Hint: you only need to make minimal changes. Neither a new field nor a new loop is necessary.)
Important: You need to change the method signature of generate to be as flexible as possible following PECS.
j shell> /open MemoList.java
2 j shell> Immutator<lnteger, Integer > incr
3 System.out.println(x +
4 return x + 1 ;
5
6 jshell> MemoList<Integer> 1 - MemoList . generate (1 e , incr)
7
8 jshell> 1. index0f(4)
9
19
11
12 3 + 1
13
14 j she 11> 1
15
16 jshell> 1. get ( 8)
17
18
19 6 + 1 28 7 + 1
21
22 jshell> 1
23 4, 5,
24
25 jshell> 1. get (2)

26 jshell> 1
27 4, 5,
28
29 jshell> 1. index0f(6) ;

39 jshell> 1
31 5,
You can test your code by running the Test 1 . java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style and can generate the documentation without error.
$ javac cs2û3Øs/fp/*java
2 $ javac -Xlint : rawtypes Test 1 . java
3 $ java Test 1
4 $ java -jar -c Aacs2û3es/bin/cs2û3e_checks.xm1
5 MemoList . java
$ javadoc -quiet -private -d docs MemoList.java
FiboLazy
The way we generate the MemoList using an Immutator does not allow us to easily generate Fibonacci sequence:
where each element is the sum of the previous two elements. To accommodate this, we need an overloaded generate method as follows:
• takes in 4 parameters:
• int n : the number of elements in the list
• T fst : the first element in the list
• T snd : the second element in the list
• Combiner < > f : a combiner
• Make sure the type is as flexible as possible
• returns a new MemoList<T> generated as:
• let fst - x and snd the result is [x, Y, f(x, y) , f(y, f ( x , y)) , y) ,
Add the overloaded generate method to the MemoList class.
• jshell> /open MemoList.java
2 jshell> Combiner<lnteger, Integer, Integer> fib = y)
3 System.out.println(x +
4 return x + Y ;
5
6 jshell> MemoList<Integer> fibL - MemoList . generate (1 1 , fib)
7 fibL
8 jshell> fibL.index0f(8)
9
19
11
12 2 + 3 13 3 + 5
14
15 jshell> fibL
16 fibL 3, 5,
17 jshell> fibL.get(8)
18 5 + 8
19 8 + 13
29 $ 21
21 jshell> fibL
22 fibL 3, 5, 8, 13, 21 ,
23 jshell> MemoList<Integer> 1 - MemoList . generate(leeeeee,
24
25
26 jshell> 1. indexOf(4)
27
28 jshell> 1
29
39 jshell> 1. get ( 8)
31
32 jshell> 1

You can test your code by running the Test2 . java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style and can generate the documentation without error.
1 $ javac cs2û3Øs/fp/*java
2 $ javac -X lint : rawtypes Test2.java
3 $ java Test2
4 $ java -jar
5 MemoList . java
$ javadoc -quiet -private -d docs cs293Ês/fp/MemoList.java
map
Now let's add a map method. The map method (lazily) applies the given Immutator on each element in the list and returns the resulting MemoList . If the element is not yet evaluated, the map method should not evaluate the element. This can be visualised as

This is, in fact, something similar to transform from Immutatorable but operated on each element of the list. The common name for this is map .
j shell> /open MemoList.java
2 j shell> import cs293ûs.fp. Immutator
3 j shell> Immutator<lnteger, Integer > incr
4 System.out.println(x +
5 return x + 1 •
6
7 j shell> Immutator<lnteger, Integer> dbl
8 System.out.println(x +
9 return X + X ;
19
11
12 j shell> MemoList<Integer> nat MemoList . generate (1 , e, incr)
13 nat
14 j shell> MemoList<Integer> even nat.map(dbl)
15 even
16 jshell> nat.index0f(3)
17
18
19
29 3
21 jshell> nat
22 nat
23 j shell>
24 even
25 j shell> // Note the 3 + 1 and comes from
26 j shell> // evaluation of nat
27 j shell> even . indexOf(1û)
28
29
39 2 2
31 3 3
32 3
33 4 4
34 4
35 5 5
36 5 jshell> nat
38 nat
39 j shell>
48 even [e, 2, 4, 6, 8, 19, ?
41 j shell> MemoList<Integer> odd = even.map(incr)
42 odd
43 j shell> // Note only forces evaluation of
44 j shell> // nat and even that are needed
45 j shell> odd. get (19)
46
47 6 + 1 48 7 + 1
49
58
51
52 28 + 1
53 21
54 jshell> nat
55 nat 3, 4, 7, 8, 9, 18, ?
56 j shell>
57 even 6, 8, ? , 29,
58 jshell> odd
59 odd 21 , ?
You can test your code by running the Test3 . java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style and can generate the documentation without error.
$ javac cs2û39s/fp/*java
2 $ javac -X lint : rawtypes Test3 . java
3 $ java Test3
4 $ java -jar N cs293es/bin/checksty1e.jar -c N cs2Ø3es/bin/cs2Ø3e_checks.xm1 5 MemoList . java
$ javadoc -quiet -private -d docs cs2Ø3ûs/fp/MemoList.java
flatMap
Now let's adda flatMap method. While the Immutator in the map method returns an element of type R , the Immutator in the flatMap method returns an element of type
MemoList<R> . So first, recap that map applies the Immutator on each element. But if the immutator is returning a MemoList , map will create a nested list. On the other hand, flapMap will flatten this nested list.
Recap the image below from recitation illustrating the behaviour of flatMap .

1 a? al1 1
no longer nested
You still need to ensure that the method signature for flatMap is as flexible as possible.
However, to simplify this, you are guaranteed that the MemoList generated by the
j shell> /open MemoList.java
2 j shell> import cs2939s.fp. Immutator
3 j shell> import cs293Ês.fp . Memo
4 j shell> Immutator<MemoList<Integer>, Integer> dupl
5 System . out . print In( " Duplicating for 6 " -times
7 return MemoList. generate(x, x, n -> x) ;
8
9 j shell> MemoList<Integer> nat = MemoList.generate(5, 1 ,
19 nat [1 ,
11 j shell> MemoList<Integer> superNat nat . flatMap(dup1)
12 Duplicating 1 for 1 -times 13 Duplicating 2 for 2-times 14 Duplicating 3 for 3-times 15 Duplicating 4 for 4-times 16 Duplicating 5 for 5-times
17 superNat
18
19 jshell> MemoList<Integer> super Even superNat.map(x
29 System . out . println( '
21 return x * 2 •
22
23 superEven
24 jshell> superEven.get(12)
25 18
26
27 jshell> super Even
28 superEven
29 jshell> superNat
39 superNat
31 jshell> nat
32
33
34 jshell> // we will show the difference with map
35 jshell> MemoList<Integer> nat2 MemoList.generate(5, 1 , x -> x + 1 )
36 nat2 jshell> MemoList<MemoList<Integer>> nestNat2 nat2 .map(dupl)
38 nestNat2
39 jshell> nestNat2.get(2)
49 Duplicating 3 for 3-times
41
42 jshell> nestNat2
43 nestNat2
44
45 jshell> for (int i=e; i<5;
46 nestNat2 .get(i) ;
47
48 Duplicating 1 for 1 -times 49 Duplicating 2 for 2-times 58 Duplicating 4 for 4-times 51 Duplicating 5 for 5-times
52 jshell> nestNat2
53 nestNat2
54
55 jshell> for (int i=Û; i<5;
56 for (int j=e;
57 nestNat2 . get (i) . get (j) ;
58
59
68 jshell> nestNat2 nestNat2 [4, 4, 4, 4] , [5, 5, 5, 5, 5] ]
You can test your code by running the Test4. java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style and can generate the documentation without error.
$ javac cs2Ø3Øs/fp/*java
2 $ javac -Xlint : rawtypes Test4.java
3 $ java Test4
4 $ java -jar
5 MemoList . java
$ javadoc -quiet -private -d docs cs2939s/fp/MemoList.java
PECS
If you have not done so, you can do a simple test on PECS by running the Test5. java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style but there is no need to generate javadoc.
1 $ javac cs2û3Øs/fp/*java
2 $ javac -Xlint : rawtypes Test5.java 3 $ java Test5
Following CS2030S Style Guide
You should make sure that your code follows the given Java style guide.
Grading
This lab is worth 16 marks and contributes 4% to your final grade. The marking scheme is as follows:
• Documentation: 2 marks
• Everything Else: 14 marks
We will deduct 1 mark for each unnecessary use of @SuppressWarnings and each raw type. @SuppressWa rnings should be used appropriately and not abused to remove compilation warnings.
Note that general style marks are no longer awarded will only be awarded for documentation. You should know how to follow the prescribed Java style by now. We will still deduct up to 2 marks if there are serious violations of styles. In other words, if you have no documentation and serious violation of styles, you will get deducted 4 marks.
Submission
Similar to Lab 6, submit the files inside the directory cs2030s/fp along with the other file without the need for folder. Your cs2030s/fp should only contain the following files:
Action . java
Actionable . java
Actually . java
Combiner . java
Constant . java
Immutator . java
Immutatorable . java
Memo . java
Additionally, you must submit the file Lab7 . h and Lab7 . java . Otherwise, you CodeCrunch submission will not run.