Difference between revisions of "ImmutableList Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
 
(32 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
=Motivation=
 +
In this assignment we will build a classic data structure from functional programming languages like [https://smlfamily.github.io/Basis/list.html SML].  It is important to think recursively in a functional programming language and so it will serve you well to approach this assignment with a recursive mind set.  Further, the fact that this data structure is immutable leads to a very clean solution.  If you find yourself going down an overly complicated road, try to imagine how you would [https://en.wikipedia.org/wiki/Lisp_(programming_language)#Lists build this assignment in the 1950s] when [https://en.wikipedia.org/wiki/IBM_704 hardware companies boasted about supporting floating point numbers].
 +
 
=Code To Investigate=
 
=Code To Investigate=
==interface [https://www.cse.wustl.edu/~cosgroved/courses/cse425s/fall20/apidocs/immutable/list/core/ImmutableList.html ImmutableList<E>]==
+
==interface [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse425s/current/apidocs/immutable/list/util/core/ImList.html ImList<E>]==
  
  <nowiki>public interface ImmutableList<E> extends Iterable<E> {
+
  <nowiki>public interface ImList<E> extends Iterable<E> {
 
/**
 
/**
 
* @return the head value if it is present
 
* @return the head value if it is present
Line 13: Line 16:
 
* @throws NoSuchElementException if empty
 
* @throws NoSuchElementException if empty
 
*/
 
*/
ImmutableList<E> tail();
+
ImList<E> tail();
  
 
/**
 
/**
Line 23: Line 26:
 
=Code To Implement=
 
=Code To Implement=
 
==Utilities==
 
==Utilities==
===Lists===
+
===ImLists===
{{JavaToImplement|Lists|nil<br/>cons<br/>brackets<br/>|immutable.list.assignment}}
+
{{JavaToImplement|ImLists|nil<br/>cons<br/>brackets<br/>|immutable.list.util.exercise}}
 +
 
 +
This class is the one required class you must support.  It creates 3 static methods which are responsible for returning instances of ImList.  There is a suggested path below involving a split implementation: one for [[#enum_EmptyImList|empty]] ImLists and one for [[#class_NonEmptyImList.3CE.3E|non-empty]] ImLists.  For now, investigate this file to see what is required and decide whether or not you want to go the suggested route.  Either way, you will want to build the supporting unshared enum and/or classes as you build these public static methods.
 +
 
 +
'''ALERT''': You do not yet need to support the iterator() method on any instance you create.  That will be the subject of a [[Iterable_Immutable_List_Assignment|future exercise]].
  
 
====nil====
 
====nil====
<pre>public static <E> ImmutableList<E> nil()</pre>
+
<pre>public static <E> ImList<E> nil()</pre>
  
Constructs a new empty list, analogous to the [http://sml-family.org/Basis/list.html#SIG:LIST.nil:TY nil constructor] for SML [http://sml-family.org/Basis/list.html List].
+
Constructs a new empty list, analogous to the [https://smlfamily.github.io/Basis/list.html#SIG:LIST.nil:TY nil constructor] for SML [https://smlfamily.github.io/Basis/list.html list] datatype.
  
 
====cons====
 
====cons====
<pre>public static <E> ImmutableList<E> cons(E head, ImmutableList<E> tail)</pre>
+
<pre>public static <E> ImList<E> cons(E head, ImList<E> tail)</pre>
  
Constructs a new list comprised of head::tail, analogous to the [http://sml-family.org/Basis/list.html#SIG:LIST.:::TY :: constructor] for SML [http://sml-family.org/Basis/list.html List].
+
Constructs a new list comprised of head::tail, analogous to the [https://smlfamily.github.io/Basis/list.html#SIG:LIST.:::TY :: constructor] for SML [https://smlfamily.github.io/Basis/list.html list] datatype.
  
 
====brackets====
 
====brackets====
<pre>public static <E> ImmutableList<E> brackets(E... elements)</pre>
+
<pre>public static <E> ImList<E> brackets(E... elements)</pre>
  
Constructs an ImmutableList<E> whose contents are defined by the elements passed in.
+
Constructs an ImList<E> whose contents are defined by the elements passed in.
  
 
The parameter <tt>E... arguments</tt> is an example usage of [https://docs.oracle.com/javase/8/docs/technotes/guides/language/varargs.html varargs] in Java.  You can treat parameter elements as if it is an <tt>E[]</tt>.  The varargs <tt>...</tt> simply allows for more convenient invocations of the <tt>brackets</tt> method.
 
The parameter <tt>E... arguments</tt> is an example usage of [https://docs.oracle.com/javase/8/docs/technotes/guides/language/varargs.html varargs] in Java.  You can treat parameter elements as if it is an <tt>E[]</tt>.  The varargs <tt>...</tt> simply allows for more convenient invocations of the <tt>brackets</tt> method.
Line 47: Line 54:
 
It is suggested that you adopt a recursive approach to solving this problem.  What is the base case?  What is the recursive case?
 
It is suggested that you adopt a recursive approach to solving this problem.  What is the base case?  What is the recursive case?
  
===enum EmptyImmutableList===
+
Note: Be sure to cons your items onto the list from the back to the front.
{{JavaToImplement|EmptyImmutableList|constructor<br/>isEmpty<br/>head<br/>tail<br/>|immutable.list.assignment}}
+
 
/* package-private */ enum EmptyImmutableList implements [https://www.cse.wustl.edu/~cosgroved/courses/cse425s/spring20/apidocs/immutable/list/core/ImmutableList.html ImmutableList<Object>]
+
=== Split Implementation Candidate ===
 +
One possible approach to supporting the public methods on Lists is a split implementation: an enum with a single enum constant to serve for all empty lists and a class for non-empty lists.
  
WARNING: you need NOT implement iterator() now. That will be the subject of a future studio.
+
<nowiki>ImList<String> a = ImLists.cons("A", ImLists.nil());
 +
ImList<String> ba = ImLists.cons("B", a);
 +
ImList<String> cba = ImLists.cons("C", ba);
 +
ImList<String> dcba = ImLists.cons("D", cba);
 +
ImList<String> edcba = ImLists.cons("E", dcba);
 +
System.out.println(edcba);</nowiki>
  
====constructor====
+
outputs:
 +
 
 +
E::D::C::B::A::[]
 +
 
 +
produces the data structure
 +
 
 +
[[File:ImList_E_D_C_B_A.svg]]
 +
 
 +
====class EmptyImList====
 +
{{JavaToImplement|EmptyImList|constructor<br/>isEmpty<br/>head<br/>tail<br/>|immutable.list.util.exercise}}
 +
<code>class EmptyImList implements [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse425s/current/apidocs/immutable/list/util/core/ImList.html ImList<Object>]</code>
 +
 
 +
'''ALERT''': you need NOT implement iterator() now.  That will be the subject of a future studio.
 +
 
 +
=====constructor=====
 
What fields, if any, are required as state for an empty list?
 
What fields, if any, are required as state for an empty list?
  
====isEmpty====
+
=====isEmpty=====
Hey EmptyImmutableList, are you empty?
+
''"Hey EmptyImList, are you empty?"''
 +
 
 +
=====head=====
 +
Check the behavior of head() dictated by the specification in [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse425s/current/apidocs/immutable/list/util/core/ImList.html#head() ImList<E>].
  
====head====
+
=====tail=====
Check the behavior of head() dictated by the specification in [https://www.cse.wustl.edu/~cosgroved/courses/cse425s/fall20/apidocs/immutable/list/core/ImmutableList.html#head() ImmutableList<E>].
+
Check the behavior of tail() dictated by the specification in [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse425s/current/apidocs/immutable/list/util/core/ImList.html#tail() ImList<E>].
  
====tail====
+
====class NonEmptyImList<E>====
Check the behavior of tail() dictated by the specification in [https://www.cse.wustl.edu/~cosgroved/courses/cse425s/fall20/apidocs/immutable/list/core/ImmutableList.html#tail() ImmutableList<E>].
+
{{JavaToImplement|NonEmptyImList|constructor<br/>isEmpty<br/>head<br/>tail<br/>|immutable.list.util.exercise}}
  
===class NonEmptyImmutableList<E>===
+
<code>final class NonEmptyImList<E> implements [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse425s/current/apidocs/immutable/list/util/core/ImList.html ImList<E>]</code>
{{JavaToImplement|NonEmptyImmutableList|constructor<br/>isEmpty<br/>head<br/>tail<br/>|immutable.list.assignment}}
 
/* package-private */ enum EmptyImmutableList implements [https://www.cse.wustl.edu/~cosgroved/courses/cse425s/spring20/apidocs/immutable/list/core/ImmutableList.html ImmutableList<Object>]
 
  
WARNING: you need NOT implement iterator() now.  That will be the subject of a future studio.
+
'''ALERT''': you need NOT implement iterator() now.  That will be the subject of a future studio.
  
====constructor====
+
=====constructor=====
 
What fields, if any, are required as state for a non-empty list?
 
What fields, if any, are required as state for a non-empty list?
  
====isEmpty====
+
=====isEmpty=====
Hey NonEmptyImmutableList, are you empty?
+
''"Hey NonEmptyImList, are you empty?"''
  
====head====
+
=====head=====
Check the behavior of head() dictated by the specification in [https://www.cse.wustl.edu/~cosgroved/courses/cse425s/fall20/apidocs/immutable/list/core/ImmutableList.html#head() ImmutableList<E>].
+
Check the behavior of head() dictated by the specification in [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse425s/current/apidocs/immutable/list/util/core/ImList.html#head() ImList<E>].
  
====tail====
+
=====tail=====
Check the behavior of tail() dictated by the specification in [https://www.cse.wustl.edu/~cosgroved/courses/cse425s/fall20/apidocs/immutable/list/core/ImmutableList.html#tail() ImmutableList<E>].
+
Check the behavior of tail() dictated by the specification in [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse425s/current/apidocs/immutable/list/util/core/ImList.html#tail() ImList<E>].
  
==Apps==
+
==Clients==
 
NOTE: Since the constructors on our implementations are package protected, you will need to use [[#nil|nil()]] and [[#cons|cons(head,tail)]].
 
NOTE: Since the constructors on our implementations are package protected, you will need to use [[#nil|nil()]] and [[#cons|cons(head,tail)]].
  
 
===Length===
 
===Length===
{{JavaToImplement|Length|length|immutable.list.apps.assignment}}
+
{{JavaToImplement|Length|length|immutable.list.clients.exercise}}
  
<pre>public static <E> int length(ImmutableList<E> list)</pre>
+
<pre>public static <E> int length(ImList<E> list)</pre>
  
Compute the length of an arbitrary ImmutableList<E>.
+
Compute the length of an arbitrary ImList<E>.
  
 
===SumProductCountdownFactorial===
 
===SumProductCountdownFactorial===
{{JavaToImplement|SumProductCountdownFactorial|sum<br/>product<br/>countdown<br/>factorial|immutable.list.apps.assignment}}
+
{{JavaToImplement|SumProductCountdownFactorial|sum<br/>product<br/>countdown<br/>factorial|immutable.list.clients.exercise}}
  
 
====sum====
 
====sum====
<pre>public static int sum(ImmutableList<Integer> xs)</pre>
+
<pre>public static int sum(ImList<Integer> xs)</pre>
  
Compute the sum of all the items in an ImmutableList<Integer>.
+
Compute the sum of all the items in an ImList<Integer>.
  
 
====product====
 
====product====
<pre>public static int product(ImmutableList<Integer> xs)</pre>
+
<pre>public static int product(ImList<Integer> xs)</pre>
  
Compute the produce all the items in an ImmutableList<Integer>.
+
Compute the produce all the items in an ImList<Integer>.
  
 
====countdown====
 
====countdown====
<pre>public static ImmutableList<Integer> countdown(int n)</pre>
+
<pre>public static ImList<Integer> countdown(int n)</pre>
  
 
Produce a new list which contains the values from n down to 1.  For example, countdown(5) would produce the list [5,4,3,2,1].
 
Produce a new list which contains the values from n down to 1.  For example, countdown(5) would produce the list [5,4,3,2,1].
Line 117: Line 145:
  
 
===Concat===
 
===Concat===
{{JavaToImplement|Concat|concat|immutable.list.apps.assignment}}
+
{{JavaToImplement|Concat|concat|immutable.list.clients.exercise}}
  
<pre>public static <E> ImmutableList<E> concat(ImmutableList<E> xs, ImmutableList<E> ys)</pre>
+
<pre>public static <E> ImList<E> concat(ImList<E> xs, ImList<E> ys)</pre>
  
 
Concatenate one list on to another.
 
Concatenate one list on to another.
  
 
=Test=
 
=Test=
{{TestSuite|ImmutableListTestSuite|immutable.list.assignment}}
+
{{TestSuite|ImListUtilAndClientsTestSuite|immutable.list}}
  
 
=Pledge, Acknowledgments, Citations=
 
=Pledge, Acknowledgments, Citations=
{{Pledge|studio-immutable-list}}
+
{{Pledge|exercise-im-list}}

Latest revision as of 12:42, 29 August 2023

Motivation

In this assignment we will build a classic data structure from functional programming languages like SML. It is important to think recursively in a functional programming language and so it will serve you well to approach this assignment with a recursive mind set. Further, the fact that this data structure is immutable leads to a very clean solution. If you find yourself going down an overly complicated road, try to imagine how you would build this assignment in the 1950s when hardware companies boasted about supporting floating point numbers.

Code To Investigate

interface ImList<E>

public interface ImList<E> extends Iterable<E> {
	/**
	 * @return the head value if it is present
	 * @throws NoSuchElementException if empty
	 */
	E head();

	/**
	 * @return the tail if it is present
	 * @throws NoSuchElementException if empty
	 */
	ImList<E> tail();

	/**
	 * @return true if empty, false otherwise
	 */
	boolean isEmpty();
}

Code To Implement

Utilities

ImLists

class: ImLists.java Java.png
methods: nil
cons
brackets
package: immutable.list.util.exercise
source folder: src/main/java

This class is the one required class you must support. It creates 3 static methods which are responsible for returning instances of ImList. There is a suggested path below involving a split implementation: one for empty ImLists and one for non-empty ImLists. For now, investigate this file to see what is required and decide whether or not you want to go the suggested route. Either way, you will want to build the supporting unshared enum and/or classes as you build these public static methods.

ALERT: You do not yet need to support the iterator() method on any instance you create. That will be the subject of a future exercise.

nil

public static <E> ImList<E> nil()

Constructs a new empty list, analogous to the nil constructor for SML list datatype.

cons

public static <E> ImList<E> cons(E head, ImList<E> tail)

Constructs a new list comprised of head::tail, analogous to the :: constructor for SML list datatype.

brackets

public static <E> ImList<E> brackets(E... elements)

Constructs an ImList<E> whose contents are defined by the elements passed in.

The parameter E... arguments is an example usage of varargs in Java. You can treat parameter elements as if it is an E[]. The varargs ... simply allows for more convenient invocations of the brackets method.

In order to build this method, consider added a private static helper method to perform the actual work.

It is suggested that you adopt a recursive approach to solving this problem. What is the base case? What is the recursive case?

Note: Be sure to cons your items onto the list from the back to the front.

Split Implementation Candidate

One possible approach to supporting the public methods on Lists is a split implementation: an enum with a single enum constant to serve for all empty lists and a class for non-empty lists.

ImList<String> a = ImLists.cons("A", ImLists.nil());
ImList<String> ba = ImLists.cons("B", a);
ImList<String> cba = ImLists.cons("C", ba);
ImList<String> dcba = ImLists.cons("D", cba);
ImList<String> edcba = ImLists.cons("E", dcba);
System.out.println(edcba);

outputs:

E::D::C::B::A::[]

produces the data structure

ImList E D C B A.svg

class EmptyImList

class: EmptyImList.java Java.png
methods: constructor
isEmpty
head
tail
package: immutable.list.util.exercise
source folder: src/main/java

class EmptyImList implements ImList<Object>

ALERT: you need NOT implement iterator() now. That will be the subject of a future studio.

constructor

What fields, if any, are required as state for an empty list?

isEmpty

"Hey EmptyImList, are you empty?"

head

Check the behavior of head() dictated by the specification in ImList<E>.

tail

Check the behavior of tail() dictated by the specification in ImList<E>.

class NonEmptyImList<E>

class: NonEmptyImList.java Java.png
methods: constructor
isEmpty
head
tail
package: immutable.list.util.exercise
source folder: src/main/java

final class NonEmptyImList<E> implements ImList<E>

ALERT: you need NOT implement iterator() now. That will be the subject of a future studio.

constructor

What fields, if any, are required as state for a non-empty list?

isEmpty

"Hey NonEmptyImList, are you empty?"

head

Check the behavior of head() dictated by the specification in ImList<E>.

tail

Check the behavior of tail() dictated by the specification in ImList<E>.

Clients

NOTE: Since the constructors on our implementations are package protected, you will need to use nil() and cons(head,tail).

Length

class: Length.java Java.png
methods: length
package: immutable.list.clients.exercise
source folder: src/main/java
public static <E> int length(ImList<E> list)

Compute the length of an arbitrary ImList<E>.

SumProductCountdownFactorial

class: SumProductCountdownFactorial.java Java.png
methods: sum
product
countdown
factorial
package: immutable.list.clients.exercise
source folder: src/main/java

sum

public static int sum(ImList<Integer> xs)

Compute the sum of all the items in an ImList<Integer>.

product

public static int product(ImList<Integer> xs)

Compute the produce all the items in an ImList<Integer>.

countdown

public static ImList<Integer> countdown(int n)

Produce a new list which contains the values from n down to 1. For example, countdown(5) would produce the list [5,4,3,2,1].

factorial

public static int factorial(int n)

Can you implement this method using the methods you have already created?

Concat

class: Concat.java Java.png
methods: concat
package: immutable.list.clients.exercise
source folder: src/main/java
public static <E> ImList<E> concat(ImList<E> xs, ImList<E> ys)

Concatenate one list on to another.

Test

class: ImListUtilAndClientsTestSuite.java Junit.png
package: immutable.list
source folder: src/test/java

Pledge, Acknowledgments, Citations

file: exercise-im-list-pledge-acknowledgments-citations.txt

More info about the Honor Pledge