import java.util.Objects;
import java.util.List;
import java.util.Arrays;
import java.util.function.BiFunction;
import java.util.function.BinaryOperator;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;
/**
* define freeze(x) (()->(x))
* define LLmake(a, b) new LazyList<>((a), freeze(b))
* define Thunk(T) Supplier<T>
*
* Thunk: The value of the parameter is calculated only when the
* function is actually called (Lazy Evaluation)
*/
public class LazyList<T> {
private static final long START_TIME = System.currentTimeMillis();
private static final long TIME_CONSUMING_OPERATION = 500;
/**
* A LazyList consists of a head of type T,
* whose tail is a Thunk(Supplier<T>) of a LazyList<T>
* The flag amIEmpty indicates if this list is empty.
*/
private final T head;
// private final Thunk(LazyList<T>) tail;
private final Supplier<LazyList<T>> tail;
private final boolean amIEmpty;
/**
* Main list constructor. But users should use the macro:
* LLmake(a, b), which is syntactic sugar for:
* new LazyList(a, freeze(b))
*
* For normal case (ie. without memoization):
* freeze(x) is syntactic sugar for: (()->(x))
* Thunk(T) is syntactic sugar for: Supplier<T>
*
* If memoization is used, then
* freeze(x) is syntactic sugar for: Memo.make(()->(x))
* Thunk(T) is syntactic sugar for Memo<T>
*
* a is Eager Evaluation
* b is Lazy Evaluation
*/
// public LazyList(T a, Thunk(LazyList<T>) b) {
public LazyList(T a, Supplier<LazyList<T>> b) {
this.head = a;
this.tail = b;
this.amIEmpty = false;
}
/**
* Private constructor of an empty list.
*/
private LazyList() {
this.head = null;
this.tail = null;
this.amIEmpty = true;
}
/**
* Convenience function to thaw a thunk.
*/
// public static <T> T thaw(Thunk(T) ice) {
public static <T> T thaw(Supplier<T> ice) {
return ice.get();
}
/**
* Create a Supplier to Supply a LazyList
*
* This freeze() method is not completely correct,
* because when freezing is called, the strategy of
* calling by value is still followed.
*
* Such as freeze(this.tail().map(f)),
* this.tail().map(f) will be executed immediately.
*
* public static <T> Supplier<LazyList<T>> freeze(LazyList<T> x) {
* return () -> {
* // Do time-consuming operation
* try {
* Thread.sleep(TIME_CONSUMING_OPERATION);
* } catch (InterruptedException e) {
* e.printStackTrace();
* }
* return x;
* };
* }
*/
/**
* Create an empty LazyList.
*/
public static <T> LazyList<T> makeEmpty() {
return new LazyList<T>();
}
/**
* Return the head of this list.
*/
public T head() {
if (this.isEmpty()) {
throw new IllegalArgumentException("head() called on empty list!");
}
return this.head;
}
/**
* Thaw the tail of the list, and return it.
*/
public LazyList<T> tail() {
if (this.isEmpty()) {
throw new IllegalArgumentException("tail() called on empty list!");
}
return thaw(Objects.requireNonNull(this.tail));
}
/**
* Return true if this list is empty, false otherwise.
*/
public boolean isEmpty() {
return this.amIEmpty;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
} else if (obj instanceof LazyList) {
LazyList<?> ll = (LazyList<?>) obj;
return this.hasSameContent(ll);
} else {
return false;
}
}
/**
* Whether the two LazyLists have the same content
*/
public boolean hasSameContent(LazyList<?> other) {
if (this.isEmpty() && other.isEmpty())
return true;
else if (!this.isEmpty() && !other.isEmpty())
return this.head().equals(other.head()) &&
this.tail().hasSameContent(other.tail());
else
return false;
}
/**
* Return a human-readable string of this list.
*/
@Override
public String toString() {
if (this.isEmpty())
return "**empty**";
return String.format("head: %s, tail: thunk! %s",
Objects.requireNonNull(this.head).toString(),
Objects.requireNonNull(this.tail).toString());
}
/**
* Print all the elements in this list. This thaws all the
* elements. If this list is infinite, then the printing
* could go on forever.
*/
public void print() {
LazyList<T> me = this;
System.out.print("(* ");
while (!me.isEmpty()) {
System.out.println(me.head() + " print executing (" +
(System.currentTimeMillis() - START_TIME) + "), ");
me = me.tail();
}
System.out.println("*)");
}
/**
* Convenience function to make a LL of multiple arguments.
*/
@SafeVarargs
public static <T> LazyList<T> fromList(T ... items) {
List<T> list = Arrays.asList(items);
return helper(list);
}
/**
* Convert a list to a LazyList
*/
private static <T> LazyList<T> helper(List<T> list) {
if (list.isEmpty()) {
return LazyList.makeEmpty();
} else {
/**
* new LazyList<T>((a), freeze(b))
* return LLmake(list.get(0), helper(list.subList(1,list.size())));
* Supplier method is freeze method.
*/
return new LazyList<T>(list.get(0),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return helper(list.subList(1,list.size()));
}
});
}
}
/**
* Apply the mapping function f onto each element of this list,
* and return a new LL containing the mapped elements.
*
* head: f(head).
* tail: pass the Function f into the tail so that the tail which is
* the next ll can call the Function f.
*
* Note: tail() is called, time-consuming operation will be evaluated,
* it means that the mapping is executing when map() is called.
*/
public <R> LazyList<R> map(Function<T,R> f) {
System.out.print("mapping executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(f.apply(this.head()), this.tail().map(f));
* Supplier method is freeze method.
*/
return new LazyList<R>(f.apply(this.head()),
new Supplier<LazyList<R>>() {
@Override
public LazyList<R> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().map(f);
}
});
}
}
/**
* Apply the mapping function f onto each element of this list, and
* return a new LL containing all the flattened mapped elements.
* Note that f produces a list for each element. But the returned
* LL flattens them all, ie. removes nested lists.
*/
public <R> LazyList<R> flatmap(Function<T, LazyList<R>> f) {
System.out.print("flatmap executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return LazyList.makeEmpty();
} else {
/**
* flatMap() should be Lazy Evaluation, but has to make it Eager Evaluation
* at here since the return type is LazyList<R>, which must execute the
* flatmap() first
*/
return f.apply(this.head())
.concat(this.tail().flatmap(f));
}
}
/**
* Return a new LL whose elements (from this list)
* pass the test of the predicate pred.
*
* Note: tail() is called, time-consuming operation will be evaluated,
* it means that the filter is executing when filter() is called.
*/
public LazyList<T> filter(Predicate<T> pred) {
System.out.print("filter executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return LazyList.makeEmpty();
}
/**
* If the head() of the ll passes the test,
* return a new ll object with current head and test its tail().
* Supplier method is freeze method.
*/
else if (pred.test(this.head())) {
return new LazyList<T>(this.head(),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().filter(pred);
}
});
}
/**
* Skip the current ll and test its tail().
*/
else {
return this.tail().filter(pred);
}
}
/**
* Return a new LL of length maxSize.
* The new list contains the same elements as this one.
*/
public LazyList<T> limit(long maxSize) {
if (maxSize == 0) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(this.head(), this.tail().limit(maxSize - 1));
* Supplier method is freeze method.
*/
return new LazyList<T>(this.head(),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().limit(maxSize - 1);
}
});
}
}
/**
* Return a new LL whose elements are the combination, element-wise,
* of this and other list. The combination is specified by the
* BinaryOperator binOp, and thus could be addition, multiplication, etc.
*/
public LazyList<T> elementWiseCombine(LazyList<T> other, BinaryOperator<T> binOp) {
System.out.print("elementWiseCombine executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty() || other.isEmpty()) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(binOp.apply(this.head(), other.head()),
* this.tail().elementWiseCombine(other.tail(), binOp));
* Supplier method is freeze method.
*/
return new LazyList<T>(binOp.apply(this.head(), other.head()),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().elementWiseCombine(other.tail(), binOp);
}
});
}
}
/**
* Return the element at position given by idx.
* idx starts from 0, and should be non-negative.
*/
public T get(int idx) {
System.out.print("get executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty() || idx < 0) {
return null;
} else if (idx == 0) {
return this.head();
} else {
return this.tail().get(idx - 1);
}
}
/**
* Convenience function: return a LazyList<Integer> of integers
* from a (inclusive) to b (exclusive)
*/
public static LazyList<Integer> intRange(int a, int b) {
System.out.print("intRange executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (a >= b) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(a, intRange(a + 1, b));
* Supplier method is freeze method.
*/
return new LazyList<Integer>(a,
new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return intRange(a + 1, b);
}
});
}
}
/**
* Concatenate other list to this one.
* Keep returning LazyList.this.tail().concat(other) until
* the current LazyList is empty, which means all the
* elements of LazyList are traversed, then return other,
* which is the concatenated LazyList.
*/
public LazyList<T> concat(LazyList<T> other) {
System.out.print("concat executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return other;
} else {
/**
* return LLmake(this.head(), this.tail().concat(other));
* Supplier method is freeze method.
*/
return new LazyList<T>(this.head(),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().concat(other);
}
});
}
}
/**
* Return a new list whose elements are those from this list,
* but in reverse order.
*
* Keep calling this.tail().tail().tail()...tail() until the tail
* is empty, then call concat()
*/
public LazyList<T> reverse() {
System.out.print("reverse executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return this;
} else {
/**
* return this.tail().reverse().concat(LLmake(this.head(), LazyList.makeEmpty()));
* Supplier method is freeze method.
*/
return this.tail()
.reverse()
.concat(new LazyList<T>(this.head(),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.makeEmpty();
}
}));
}
}
/**
* Combine this LazyList with other, using generic combiner.
* This may be used to generate cartesian product of the 2 lists.
*/
public <U,R> LazyList<R> combine(LazyList<U> other, BiFunction<T,U,R> combiner) {
return this.flatmap(x ->
other.map(y -> combiner.apply(x,y)));
}
/**
* Invoke the consumer eat on every element in this list.
* This is an eager operation: the entire list will be thawed.
*/
public void forEach(Consumer<T> eat) {
if (!this.isEmpty()) {
eat.accept(this.head());
this.tail().forEach(eat);
}
}
/**
* Accumulate all the elements in this list, using the accumulator and identity.
* This is an eager operation: the entire list will be thawed.
*/
public T reduce(T identity, BinaryOperator<T> accumulator) {
System.out.print("reduce executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return identity;
} else {
return accumulator.apply(this.head(),
this.tail().reduce(identity,
accumulator));
}
}
/**
* Add the elements in two LazyLists in order
*/
public LazyList<T> add(LazyList<T> other, BinaryOperator<T> add) {
if (this.isEmpty() || other.isEmpty()) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(add.apply(this.head(), other.head()),
* this.tail().add(other.tail(), add));
* Supplier method is freeze method.
*/
return new LazyList<T>(add.apply(this.head(), other.head()),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
return LazyList.this.tail().add(other.tail(), add);
}
});
}
}
/**
* Create an integer LazyList start from n, must set limit()
*/
public static LazyList<Integer> integersFrom(int n) {
System.out.print("integersFrom executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
/**
* return LLmake(n, integersFrom(n + 1));
* Supplier method is freeze method.
*/
return new LazyList<Integer>(n,
new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
return integersFrom(n + 1);
}
});
}
/**
* Sieve Prime
*/
public static LazyList<Integer> sieve(LazyList<Integer> s) {
System.out.print("sieve executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
/**
* return LLmake(s.head(), sieve(s.tail().filter(x-> (x % s.head()) != 0)));
* Supplier method is freeze method.
*/
return new LazyList<Integer>(s.head(),
new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
return sieve(s.tail().filter(x-> (x % s.head()) != 0));
}
});
}
}
import java.util.Objects;
import java.util.function.Supplier;
import java.util.TreeMap;
public class Memo<T> {
private static final TreeMap<String, Integer> getTable = new TreeMap<>();
public static void printGetTable() {
System.out.println("Memo Get Table: ");
// Print all keys and values
getTable.forEach((k, v) -> System.out.printf("%s: count-> %d%n", k, v));
}
private boolean hasBeenRun;
private T value;
private final Supplier<T> supplier;
private Memo(Supplier<T> s) {
this.hasBeenRun = false;
this.value = null;
this.supplier = s;
}
/**
* Return new Memo Object with Supplier Object
*/
public static <T> Memo<T> make(Supplier<T> s) {
return new Memo<>(Objects.requireNonNull(s));
}
public T get() {
if (!hasBeenRun) {
this.hasBeenRun = true;
this.value = this.supplier.get();
}
/**
* If the key does not exist, a new key will be created with this key name,
* the value of this key is 1 by default, and this new key-value pair will be added to the TreeMap table
* otherwise, the value of this key will add 1
*
* x: old value of the key
* y: new value of the key
*/
getTable.merge(this.value.toString(), 1, (x, y) -> x + 1);
return this.value;
}
}
import java.util.Objects;
import java.util.List;
import java.util.Arrays;
import java.util.function.BiFunction;
import java.util.function.BinaryOperator;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;
/**
* define freeze(x) Memo.make(()->(x))
* define LLmake(a, b) new LazyList<>((a), freeze(b))
* define Thunk(T) Memo<T>
*
* Thunk: The value of the parameter is calculated only when the
* function is actually called (Lazy Evaluation)
*/
public class MemoLazyList<T> {
private static final long START_TIME = System.currentTimeMillis();
private static final long TIME_CONSUMING_OPERATION = 500;
/**
* A LazyList consists of a head of type T,
* whose tail is a Thunk(Supplier<T>) of a LazyList<T>
* The flag amIEmpty indicates if this list is empty.
*/
private final T head;
// private final Thunk(LazyList<T>) tail;
private final Memo<MemoLazyList<T>> tail;
private final boolean amIEmpty;
/**
* Main list constructor. But users should use the macro:
* LLmake(a, b), which is syntactic sugar for:
* new LazyList(a, freeze(b))
*
* For normal case (ie. without memoization):
* freeze(x) is syntactic sugar for: (()->(x))
* Thunk(T) is syntactic sugar for: Supplier<T>
*
* If memoization is used, then
* freeze(x) is syntactic sugar for: Memo.make(()->(x))
* Thunk(T) is syntactic sugar for Memo<T>
*
* a is Eager Evaluation
* b is Lazy Evaluation
*/
// public LazyList(T a, Thunk(LazyList<T>) b) {
public MemoLazyList(T a, Memo<MemoLazyList<T>> b) {
this.head = a;
this.tail = b;
this.amIEmpty = false;
}
/**
* Private constructor of an empty list.
*/
private MemoLazyList() {
this.head = null;
this.tail = null;
this.amIEmpty = true;
}
/**
* Convenience function to thaw a thunk.
*/
// public static <T> T thaw(Thunk(T) ice) {
public static <T> T thaw(Memo<T> ice) {
return ice.get();
}
/**
* Create a Supplier to Supply a LazyList
*
* This freeze() method is not completely correct,
* because when freezing is called, the strategy of
* calling by value is still followed.
*
* Such as freeze(this.tail().map(f)),
* this.tail().map(f) will be executed immediately.
*
* public static <T> Supplier<LazyList<T>> freeze(LazyList<T> x) {
* return () -> {
* // Do time-consuming operation
* try {
* Thread.sleep(TIME_CONSUMING_OPERATION);
* } catch (InterruptedException e) {
* e.printStackTrace();
* }
* return x;
* };
* }
*/
/**
* Create an empty LazyList.
*/
public static <T> MemoLazyList<T> makeEmpty() {
return new MemoLazyList<T>();
}
/**
* Return the head of this list.
*/
public T head() {
if (this.isEmpty()) {
throw new IllegalArgumentException("head() called on empty list!");
}
return this.head;
}
/**
* Thaw the tail of the list, and return it.
*/
public MemoLazyList<T> tail() {
if (this.isEmpty()) {
throw new IllegalArgumentException("tail() called on empty list!");
}
return thaw(Objects.requireNonNull(this.tail));
}
/**
* Return true if this list is empty, false otherwise.
*/
public boolean isEmpty() {
return this.amIEmpty;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
} else if (obj instanceof MemoLazyList) {
MemoLazyList<?> ll = (MemoLazyList<?>) obj;
return this.hasSameContent(ll);
} else {
return false;
}
}
/**
* Whether the two LazyLists have the same content
*/
public boolean hasSameContent(MemoLazyList<?> other) {
if (this.isEmpty() && other.isEmpty())
return true;
else if (!this.isEmpty() && !other.isEmpty())
return this.head().equals(other.head()) &&
this.tail().hasSameContent(other.tail());
else
return false;
}
/**
* Return a human-readable string of this list.
*/
@Override
public String toString() {
if (this.isEmpty())
return "**empty**";
return String.format("head: %s, tail: thunk! %s",
Objects.requireNonNull(this.head).toString(),
Objects.requireNonNull(this.tail).toString());
}
/**
* Print all the elements in this list. This thaws all the
* elements. If this list is infinite, then the printing
* could go on forever.
*/
public void print() {
MemoLazyList<T> me = this;
System.out.print("(* ");
while (!me.isEmpty()) {
System.out.println(me.head() + " print executing (" +
(System.currentTimeMillis() - START_TIME) + "), ");
me = me.tail();
}
System.out.println("*)");
}
/**
* Convenience function to make a LL of multiple arguments.
*/
@SafeVarargs
public static <T> MemoLazyList<T> fromList(T ... items) {
List<T> list = Arrays.asList(items);
return helper(list);
}
/**
* Convert a list to a LazyList
*/
private static <T> MemoLazyList<T> helper(List<T> list) {
if (list.isEmpty()) {
return MemoLazyList.makeEmpty();
} else {
/**
* new LazyList<T>((a), freeze(b))
* return LLmake(list.get(0), helper(list.subList(1,list.size())));
* Supplier method is freeze method.
*/
return new MemoLazyList<T>(list.get(0), Memo.make(
new Supplier<MemoLazyList<T>>() {
@Override
public MemoLazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return helper(list.subList(1,list.size()));
}
}));
}
}
/**
* Apply the mapping function f onto each element of this list,
* and return a new LL containing the mapped elements.
*
* head: f(head).
* tail: pass the Function f into the tail so that the tail which is
* the next ll can call the Function f.
*
* Note: tail() is called, time-consuming operation will be evaluated,
* it means that the mapping is executing when map() is called.
*/
public <R> MemoLazyList<R> map(Function<T,R> f) {
System.out.print("mapping executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return MemoLazyList.makeEmpty();
} else {
/**
* return LLmake(f.apply(this.head()), this.tail().map(f));
* Supplier method is freeze method.
*/
return new MemoLazyList<R>(f.apply(this.head()), Memo.make(
new Supplier<MemoLazyList<R>>() {
@Override
public MemoLazyList<R> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return MemoLazyList.this.tail().map(f);
}
}));
}
}
/**
* Apply the mapping function f onto each element of this list, and
* return a new LL containing all the flattened mapped elements.
* Note that f produces a list for each element. But the returned
* LL flattens them all, ie. removes nested lists.
*/
public <R> MemoLazyList<R> flatmap(Function<T, MemoLazyList<R>> f) {
System.out.print("flatmap executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return MemoLazyList.makeEmpty();
} else {
return f.apply(this.head())
.concat(this.tail().flatmap(f));
}
}
/**
* Return a new LL whose elements (from this list)
* pass the test of the predicate pred.
*
* Note: tail() is called, time-consuming operation will be evaluated,
* it means that the filter is executing when filter() is called.
*/
public MemoLazyList<T> filter(Predicate<T> pred) {
System.out.print("filter executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return MemoLazyList.makeEmpty();
}
/**
* If the head() of the ll passes the test,
* return a new ll object with current head and test its tail().
* Supplier method is freeze method.
*/
else if (pred.test(this.head())) {
return new MemoLazyList<T>(this.head(), Memo.make(
new Supplier<MemoLazyList<T>>() {
@Override
public MemoLazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return MemoLazyList.this.tail().filter(pred);
}
}));
}
/**
* Skip the current ll and test its tail().
*/
else {
return this.tail().filter(pred);
}
}
/**
* Return a new LL of length maxSize.
* The new list contains the same elements as this one.
*/
public MemoLazyList<T> limit(long maxSize) {
if (maxSize == 0) {
return MemoLazyList.makeEmpty();
} else {
/**
* return LLmake(this.head(), this.tail().limit(maxSize - 1));
* Supplier method is freeze method.
*/
return new MemoLazyList<T>(this.head(), Memo.make(
new Supplier<MemoLazyList<T>>() {
@Override
public MemoLazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return MemoLazyList.this.tail().limit(maxSize - 1);
}
}));
}
}
/**
* Return a new LL whose elements are the combination, element-wise,
* of this and other list. The combination is specified by the
* BinaryOperator binOp, and thus could be addition, multiplication, etc.
*/
public MemoLazyList<T> elementWiseCombine(MemoLazyList<T> other, BinaryOperator<T> binOp) {
System.out.print("elementWiseCombine executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty() || other.isEmpty()) {
return MemoLazyList.makeEmpty();
} else {
/**
* return LLmake(binOp.apply(this.head(), other.head()),
* this.tail().elementWiseCombine(other.tail(), binOp));
* Supplier method is freeze method.
*/
return new MemoLazyList<T>(binOp.apply(this.head(), other.head()), Memo.make(
new Supplier<MemoLazyList<T>>() {
@Override
public MemoLazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return MemoLazyList.this.tail().elementWiseCombine(other.tail(), binOp);
}
}));
}
}
/**
* Return the element at position given by idx.
* idx starts from 0, and should be non-negative.
*/
public T get(int idx) {
System.out.print("get executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty() || idx < 0) {
return null;
} else if (idx == 0) {
return this.head();
} else {
return this.tail().get(idx - 1);
}
}
/**
* Convenience function: return a LazyList<Integer> of integers
* from a (inclusive) to b (exclusive)
*/
public static MemoLazyList<Integer> intRange(int a, int b) {
System.out.print("intRange executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (a >= b) {
return MemoLazyList.makeEmpty();
} else {
/**
* return LLmake(a, intRange(a + 1, b));
* Supplier method is freeze method.
*/
return new MemoLazyList<Integer>(a, Memo.make(
new Supplier<MemoLazyList<Integer>>() {
@Override
public MemoLazyList<Integer> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return intRange(a + 1, b);
}
}));
}
}
/**
* Concatenate other list to this one.
* Keep returning LazyList.this.tail().concat(other) until
* the current LazyList is empty, which means all the
* elements of LazyList are traversed, then return other,
* which is the concatenated LazyList.
*/
public MemoLazyList<T> concat(MemoLazyList<T> other) {
System.out.print("concat executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return other;
} else {
/**
* return LLmake(this.head(), this.tail().concat(other));
* Supplier method is freeze method.
*/
return new MemoLazyList<T>(this.head(), Memo.make(
new Supplier<MemoLazyList<T>>() {
@Override
public MemoLazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return MemoLazyList.this.tail().concat(other);
}
}));
}
}
/**
* Return a new list whose elements are those from this list,
* but in reverse order.
*
* Keep calling this.tail().tail().tail()...tail() until the tail
* is empty, then call concat()
*/
public MemoLazyList<T> reverse() {
System.out.print("reverse executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return this;
} else {
/**
* return this.tail().reverse().concat(LLmake(this.head(), LazyList.makeEmpty()));
* Supplier method is freeze method.
*/
return this.tail()
.reverse()
.concat(new MemoLazyList<T>(this.head(), Memo.make(
new Supplier<MemoLazyList<T>>() {
@Override
public MemoLazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return MemoLazyList.makeEmpty();
}
})));
}
}
/**
* Combine this LazyList with other, using generic combiner.
* This may be used to generate cartesian product of the 2 lists.
*/
public <U,R> MemoLazyList<R> combine(MemoLazyList<U> other, BiFunction<T,U,R> combiner) {
return this.flatmap(x ->
other.map(y -> combiner.apply(x,y)));
}
/**
* Invoke the consumer eat on every element in this list.
* This is an eager operation: the entire list will be thawed.
*/
public void forEach(Consumer<T> eat) {
if (!this.isEmpty()) {
eat.accept(this.head());
this.tail().forEach(eat);
}
}
/**
* Accumulate all the elements in this list, using the accumulator and identity.
* This is an eager operation: the entire list will be thawed.
*/
public T reduce(T identity, BinaryOperator<T> accumulator) {
System.out.print("reduce executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return identity;
} else {
return accumulator.apply(this.head(),
this.tail().reduce(identity,
accumulator));
}
}
/**
* Add the elements in two LazyLists in order
*/
public MemoLazyList<T> add(MemoLazyList<T> other, BinaryOperator<T> add) {
if (this.isEmpty() || other.isEmpty()) {
return MemoLazyList.makeEmpty();
} else {
/**
* return LLmake(add.apply(this.head(), other.head()),
* this.tail().add(other.tail(), add));
* Supplier method is freeze method.
*/
return new MemoLazyList<T>(add.apply(this.head(), other.head()), Memo.make(
new Supplier<MemoLazyList<T>>() {
@Override
public MemoLazyList<T> get() {
return MemoLazyList.this.tail().add(other.tail(), add);
}
}));
}
}
/**
* Create an integer LazyList start from n, must set limit()
*/
public static MemoLazyList<Integer> integersFrom(int n) {
System.out.print("integersFrom executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
/**
* return LLmake(n, integersFrom(n + 1));
* Supplier method is freeze method.
*/
return new MemoLazyList<Integer>(n, Memo.make(
new Supplier<MemoLazyList<Integer>>() {
@Override
public MemoLazyList<Integer> get() {
return integersFrom(n + 1);
}
}));
}
/**
* Sieve Prime
*/
public static MemoLazyList<Integer> sieve(MemoLazyList<Integer> s) {
System.out.print("sieve executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
/**
* return LLmake(s.head(), sieve(s.tail().filter(x-> (x % s.head()) != 0)));
* Supplier method is freeze method.
*/
return new MemoLazyList<Integer>(s.head(), Memo.make(
new Supplier<MemoLazyList<Integer>>() {
@Override
public MemoLazyList<Integer> get() {
return sieve(s.tail().filter(x-> (x % s.head()) != 0));
}
}));
}
/**
* Fibonacci numbers
* LazyList<Integer> fib;
* fib = LLmake(0, LLmake(1, fib.add(fib.tail(), (x, y) -> x + y)));
*/
}
import java.time.Duration;
import java.time.Instant;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;
public class LLTest {
public static <T> Predicate<T> predInstrument(Predicate<T> p, String msg) {
/**
* return new Predicate<T>() {
* @Override
* public boolean test(T x) {
* System.out.println(msg + x);
* return p.test(x);
* }
* };
*/
return x -> {
System.out.println(msg + x);
return p.test(x);
};
}
public static <T, U> Function<T, U> funcInstrument(Function<T, U> f, String msg) {
/**
* return new Function<T, U>() {
* @Override
* public U apply(T x) {
* System.out.println(msg + x);
* return f.apply(x);
* }
* }
*/
return x-> {
System.out.println(msg + x);
return f.apply(x);
};
}
public static <T> T timeIt(Supplier<T> s, String msg) {
Instant start, end;
long timeTaken;
T value;
start = Instant.now();
value = s.get();
end = Instant.now();
timeTaken = Duration.between(start,end).toMillis();
System.out.printf("%s took %d ms%n",
msg,
timeTaken);
return value;
}
public static void main(String[] args) {
initExample();
printExample();
mapExample();
flatMapExample();
filterExample();
addExample();
elementWiseCombineExample();
reduceExample();
sieveExample();
fibonacciExample();
fibonacciMemoExample();
}
public static void initExample() {
/**
* LazyList<Integer> ll1 = new LazyList<Integer>(1,
* new Supplier<LazyList<Integer>>() {
* @Override
* public LazyList<Integer> get() {
* return new LazyList<Integer>(2,
* new Supplier<LazyList<Integer>>() {
* @Override
* public LazyList<Integer> get() {
* return LazyList.makeEmpty();
* }
* });
* }
* });
*/
/**
* Further simplify
*/
// Step 1:
LazyList<Integer> ll1 = new LazyList<Integer>(1,
// Step 6:
() -> new LazyList<Integer>(2, LazyList::makeEmpty));
/**
* Only ll1 object will be created fist, ll2 and ll3 will be created
* when the tail() is called.
*/
// Step 2:
System.out.println("ll1: " + ll1);
// Step 3:
System.out.println("ll1.head(): " + ll1.head());
// Step 4:
System.out.println("ll2 will not be evaluated before the l1.tail() is called");
// Step 5:
System.out.println("ll1.tail(): " + ll1.tail());
}
public static void printExample() {
/**
* print ll1.head(), call ll1.tail(), evaluate ll2 at this time,
* print ll2.head(), call ll2.tail(), evaluate ll3 at this time,
* ...
* print ll5.head(), call ll5.tail(), ll6 is empty, end.
*/
LazyList<Integer> lll = LazyList.intRange(1, 5);
lll.print();
}
public static void mapExample() {
/**
* 1. Recursively execute intRange()
* 2. Recursively execute map()
*
* print ll1.head(), call ll1.tail(), evaluate ll2 at this time,
* print ll2.head(), call ll2.tail(), evaluate ll3 at this time,
* ...
* print ll5.head(), call ll5.tail(), ll6 is empty, end.
*/
LazyList.intRange(1, 5).map(x -> x * x).print();
}
public static void flatMapExample() {
/**
* Flatten the LazyList of LazyList to LazyList
*
* 1. Recursively execute flatmap()
* 2. Recursively execute concat()
* LazyList.fromList(1, 2, 3, 4, 5) -- concat --> LazyList.fromList(6, 7, 8, 9, 10) -- concat -->
* LazyList.fromList(11, 12, 13, 14, 15) -- concat --> LazyList.fromList(16, 17, 18, 19, 20)
* Equivalently:
* new LazyList<>((1), freeze(2)) -- concat --> new LazyList<>((6), freeze(7)) -- concat -->
* new LazyList<>((11), freeze(12)) -- concat --> new LazyList<>((16), freeze(17))
* Then we can get a flattened list "fll"
*
* From the source code of concat(), we know that the concat() will be called when the tail()
* is called each time until the tail() is empty, then connect the tail to another LazyList.
* So when the print is called:
* print fll1.head(), call fll1.tail(),
* call fll1.concat(), print fll2.head(), call fll2.tail(),
* ...
* call fll20.concat(), print fll20.head(), call fll20.tail(), fll20 is empty, end.
*/
LazyList.fromList(
LazyList.fromList(1, 2, 3, 4, 5),
LazyList.fromList(6, 7, 8, 9, 10),
LazyList.fromList(11, 12, 13, 14, 15),
LazyList.fromList(16, 17, 18, 19, 20)
).flatmap(x -> x).print();
}
public static void filterExample() {
/**
* 1. Recursively execute intRange()
* 2. Recursively execute filter()
* 3. Recursively execute map()
*
* print ll1.head(), call ll1.tail(), evaluate ll2 at this time,
* print ll2.head(), call ll2.tail(), evaluate ll3 at this time,
* ...
* print ll5.head(), call ll5.tail(), ll6 is empty, end.
*/
LazyList.intRange(1, 5).filter(predInstrument(x -> x % 2 == 0, "FILTER: ")).map(x -> x * x).print();
}
public static void addExample() {
/**
* 1. Recursively execute intRange() in two LazyLists
* 2. Recursively execute add()
*
* Evaluate the add() between two elements in two LazyLists, and print the result
*/
LazyList.intRange(1, 5).add(LazyList.intRange(1, 10), Integer::sum).print();
}
public static void elementWiseCombineExample() {
/**
* 1 + 5 = 6, 2 + 5 = 7, 3 + 5 = 8, 4 + 5 = 9
*
* 1. Recursively execute intRange()
* 2. Recursively execute map()
*
* Evaluate the elementWiseCombine() between two elements in two LazyLists, and print the result
*/
LazyList<Integer> ll = LazyList.intRange(1, 5);
LazyList<Integer> twos = ll.map(x -> 5);
ll.elementWiseCombine(twos, Integer::sum).print();
}
public static void reduceExample() {
/**
* 1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 = 30
*
* 1. Recursively execute intRange()
* 2. Recursively execute map()
*
* Evaluate the reduce() between the current element in the LazyList and the accumulated result
*/
int result = LazyList.intRange(1, 5)
.map(x -> x * x)
.reduce(0, Integer::sum);
System.out.println(result);
/**
* Factorial
* 1 * 2 * 3 * 4 = 24
*
* 1. Recursively execute intRange()
* 2. Recursively execute map()
*
* Evaluate the reduce() between the current element in the LazyList and the accumulated result
*/
int factorial = LazyList.intRange(1, 5)
.reduce(1, (x, y) -> x * y);
System.out.println(factorial);
}
public static void sieveExample() {
/**
* Find the first 5 primes
*/
LazyList<Integer> primes = LazyList.sieve(LazyList.integersFrom(2));
primes.limit(5).print();
}
public static LazyList<Integer> fib;
public static void fibonacciExample() {
// 0, 1, 1, 2, 3, 5, 8, 13, 21 ...
fib = new LazyList<Integer>(0,
new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
return new LazyList<Integer>(1,
new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
return fib.elementWiseCombine(fib.tail(),
Integer::sum);
}
});
}
});
timeIt(()-> fib.get(5), "fib 5");
timeIt(()-> fib.get(6), "fib 6");
timeIt(()-> fib.get(7), "fib 7");
}
public static MemoLazyList<Integer> fibMemo;
public static void fibonacciMemoExample() {
// 0, 1, 1, 2, 3, 5, 8, 13, 21 ...
fibMemo = new MemoLazyList<Integer>(0, Memo.make(
new Supplier<MemoLazyList<Integer>>() {
@Override
public MemoLazyList<Integer> get() {
return new MemoLazyList<Integer>(1, Memo.make(
new Supplier<MemoLazyList<Integer>>() {
@Override
public MemoLazyList<Integer> get() {
return fibMemo.elementWiseCombine(fibMemo.tail(),
Integer::sum);
}
}));
}
}));
timeIt(()-> fibMemo.get(5), "fib 5");
timeIt(()-> fibMemo.get(6), "fib 6");
timeIt(()-> fibMemo.get(7), "fib 7");
}
}
/* Oputput */
// initExample
ll1: head: 1, tail: thunk! nus.cs2030.lazyevaluation.LLTest$$Lambda$16/0x0000000800b95040@7cc355be
ll1.head(): 1
ll2 will not be evaluated before the l1.tail() is called
ll1.tail(): head: 2, tail: thunk! nus.cs2030.lazyevaluation.LLTest$$Lambda$21/0x0000000800b96840@3941a79c
// printExample
(* 1 print executing (0), 2 print executing (509), 3 print executing (1012), 4 print executing (1516), *)
// mapExample
intRange executing (0) mapping executing (5) (* 1 print executing (6),
intRange executing (1037) mapping executing (1037) 4 print executing (1037),
intRange executing (2064) mapping executing (2064) 9 print executing (2064),
intRange executing (3090) mapping executing (3090) 16 print executing (3090),
intRange executing (4105) mapping executing (4105) *)
// flatMapExample
flatmap executing (0) flatmap executing (509) flatmap executing (1022) flatmap executing (1537)
flatmap executing (2051) concat executing (2051) concat executing (2053) concat executing (2053)
concat executing (2053) (* 1 print executing (2054),
concat executing (3093) 2 print executing (3093),
concat executing (4117) 3 print executing (4117),
concat executing (5143) 4 print executing (5143),
concat executing (6159) 5 print executing (6159),
concat executing (7187) 6 print executing (7187),
concat executing (8216) 7 print executing (8216),
concat executing (9241) 8 print executing (9241),
concat executing (10254) 9 print executing (10254),
concat executing (11266) 10 print executing (11266),
concat executing (12294) 11 print executing (12294),
concat executing (13319) 12 print executing (13319),
concat executing (14331) 13 print executing (14331),
concat executing (15335) 14 print executing (15335),
concat executing (16350) 15 print executing (16350),
concat executing (17364) 16 print executing (17364),
concat executing (18382) 17 print executing (18382),
concat executing (19408) 18 print executing (19408),
concat executing (20413) 19 print executing (20413),
concat executing (21439) 20 print executing (21439),
concat executing (22468) *)
// filterExample
intRange executing (0) filter executing (10) FILTER: 1
intRange executing (524) filter executing (524) FILTER: 2
mapping executing (546) (* 4 print executing (550),
intRange executing (2088) filter executing (2088) FILTER: 3
intRange executing (2603) filter executing (2603) FILTER: 4
mapping executing (2603) 16 print executing (2603),
intRange executing (4147) filter executing (4147) mapping executing (4147) *)
// addExample
intRange executing (0) intRange executing (10) (* 2 print executing (15),
intRange executing (527) intRange executing (1042) 4 print executing (1042),
intRange executing (1558) intRange executing (2072) 6 print executing (2072),
intRange executing (2585) intRange executing (3087) 8 print executing (3087),
intRange executing (3589) intRange executing (4104) *)
// elementWiseCombineExample
intRange executing (0) mapping executing (5) elementWiseCombine executing (10) (* 6 print executing (15),
intRange executing (1046) intRange executing (2060) mapping executing (2060) elementWiseCombine executing (2060)
7 print executing (2060),
intRange executing (3076) intRange executing (4089) mapping executing (4089) elementWiseCombine executing (4089)
8 print executing (4089),
intRange executing (5106) intRange executing (6118) mapping executing (6118) elementWiseCombine executing (6118)
9 print executing (6118),
intRange executing (7144) intRange executing (8160) mapping executing (8160) elementWiseCombine executing (8160) *)
// reduceExample
intRange executing (0) mapping executing (5) reduce executing (6)
intRange executing (1031) mapping executing (1031) reduce executing (1031)
intRange executing (2048) mapping executing (2048) reduce executing (2048)
intRange executing (3074) mapping executing (3074) reduce executing (3074)
intRange executing (4100) mapping executing (4100) reduce executing (4100) 30
intRange executing (4100) reduce executing (4101)
intRange executing (4616) reduce executing (4616)
intRange executing (5117) reduce executing (5117)
intRange executing (5627) reduce executing (5627)
intRange executing (6127) reduce executing (6127) 24
// sieveExample
integersFrom executing (0) sieve executing (8) (* 2 print executing (17),
integersFrom executing (525) filter executing (525) sieve executing (548) 3 print executing (548),
integersFrom executing (1567) filter executing (1567)
integersFrom executing (1567) filter executing (1567) filter executing (1567)
sieve executing (1567) 5 print executing (1567),
integersFrom executing (3093) filter executing (3093)
integersFrom executing (3093) filter executing (3093) filter executing (3093) filter executing (3093)
sieve executing (3093) 7 print executing (3093),
integersFrom executing (5137) filter executing (5137)
integersFrom executing (5137) filter executing (5137) filter executing (5137)
integersFrom executing (5650) filter executing (5650)
integersFrom executing (5650) filter executing (5650) filter executing (5650) filter executing (5650)
filter executing (5650)
sieve executing (5650) 11 print executing (5650),
integersFrom executing (8206) filter executing (8206)
integersFrom executing (8206) filter executing (8206) filter executing (8206) filter executing (8206)
filter executing (8206) filter executing (8206)
sieve executing (8206) *)
// fibonacciExample
fib 5 took 3554 ms
fib 6 took 7132 ms
fib 7 took 13240 ms
// fibonacciMemoExample
fib 5 took 1549 ms
fib 6 took 513 ms
fib 7 took 512 ms