Skip to content

Instantly share code, notes, and snippets.

@mchericoni

mchericoni/Empty.java

Last active August 29, 2015 14:18
Show Gist options
  • Save mchericoni/c0c39921c6d4ef89e97c to your computer and use it in GitHub Desktop.
Save mchericoni/c0c39921c6d4ef89e97c to your computer and use it in GitHub Desktop.
Download ZIP
Java 8 Lazy Lists
Raw
Empty.java
import java.util.function.Predicate;
public class Empty<T> implements LazyList<T> {
@Override
public T head() {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public LazyList<T> tail() {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public LazyList<T> filter(Predicate<? super T> p) {
return this;
}
@Override
public LazyList<T> takeWhile(Predicate<? super T> p) {
return this;
}
}
Raw
LazyLinkedList.java
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.Supplier;
public class LazyLinkedList<T> implements LazyList<T> {
final T head;
/**
* The tail is not itself a list but a {@link Supplier} that returns the
* next node only on demand when invoked.
*/
final Supplier<LazyList<T>> tail;
public LazyLinkedList(T head, Supplier<LazyList<T>> tail) {
this.head = head;
this.tail = tail;
}
@Override
public T head() {
return head;
}
@Override
public LazyList<T> tail() {
return tail.get();
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public LazyList<T> filter(Predicate<? super T> p) {
return p.test(head()) ? new LazyLinkedList<>(head(), () -> tail().filter(p)) : tail().filter(p);
}
@Override
public LazyList<T> takeWhile(Predicate<? super T> p) {
return p.test(head()) ? new LazyLinkedList<>(head(), () -> tail().takeWhile(p)) : new Empty<>();
}
@Override
public void forEach(Consumer<? super T> consumer) {
consumer.accept(head());
tail().forEach(consumer);
}
}
Raw
LazyList.java
import java.util.function.Consumer;
import java.util.function.Predicate;
public interface LazyList<T> {
T head();
LazyList<T> tail();
default boolean isEmpty() {
return true;
}
LazyList<T> filter(Predicate<? super T> p);
LazyList<T> takeWhile(Predicate<? super T> p);
public default void forEach(Consumer<? super T> consumer) {
// Empty default implementation
}
}
Raw
LazyListTest.java
import org.junit.Assert;
import org.junit.Test;
public class LazyListTest {
// infinite lazy list of numbers starting from n
public static LazyList<Integer> from(int n) {
return new LazyLinkedList<>(n, () -> from(n + 1));
}
// Sieve of Eratosthenes
public static LazyList<Integer> sieve(LazyList<Integer> s) {
return new LazyLinkedList<>(s.head(), () -> sieve(s.tail().filter(n -> n % s.head() != 0)));
}
@Test
public void testLazyLinkedList() {
LazyList<Integer> l = new LazyLinkedList<>(7, () -> new LazyLinkedList<>(10,
() -> new Empty<>())); // 7 -> 10 -> Empty
Assert.assertEquals((Integer) 7, l.head());
Assert.assertFalse(l.tail().isEmpty());
Assert.assertEquals((Integer) 10, l.tail().head());
Assert.assertTrue(l.tail().tail().isEmpty());
Assert.assertFalse(l.filter(n -> n % 2 == 0).isEmpty());
Assert.assertTrue(l.filter(n -> n < 0).isEmpty());
// Even numbers from 5 to 10
from(5).filter(n -> n % 2 == 0).takeWhile(n -> n <= 10).forEach(System.out::println);
// Prime numbers below 20
sieve(from(2)).takeWhile(n -> n < 20).forEach(System.out::println);
// This will eventually fail with a java.lang.StackOverflowError
// sieve(from(2)).forEach(System.out::println);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment