Infinite streams give you the illusion that it can contain infinite number of objects. The real kludge behind infinite streams is lazy evaluation. SICP introduces the term delayed evaluation, which enables us to represent very large (even infinite) sequences as streams. Functional languages like Haskell and Miranda employs laziness as the default paradigm of evaluation, while languages like Scheme implement the same concepts as library functions (delay and force).
Dominik Gruntz implements infinite streams in Java using the functor paradigm and inner classes. The obvious problem is verbosity resulting from the accidental complexity that they lend to the implementation. In this post, I attempt the same using Neal's closures prototype. So, without further ado ..
The Stream Interface
Here's the contract for lazy evaluation ..
class StreamTest {
interface Stream<E> {
E car();
Stream<E> cdr();
E get(int index);
<R> Stream<R> map(Unary<? super E, R> f);
Stream<E> filter(Unary<? super E, Boolean> f);
}
//..
}
and a lazy implementation using Java closures ..
class StreamTest {
interface Stream<E> {
//.. as above
}
static class LazyStream<E> implements Stream<E> {
private E car;
private {=>Stream<E>} cdr;
// constructor
public LazyStream(E car, {=>Stream<E>} cdr) {
this.car = car;
this.cdr = cdr;
}
// accessors
public E car() { return car; }
public Stream<E> cdr() { return cdr.invoke(); }
// access at position
public E get(int index) {
Stream<E> stream = this;
while (index-- > 0) {
stream = stream.cdr();
}
return stream.car();
}
// map over the stream
public <R> Stream<R> map(Unary<? super E, R> f) {
return cons(f.invoke(car), {=>cdr().map(f)});
}
// filter the stream
public Stream<E> filter(Unary<? super E, Boolean> f) {
if (car() != null) {
if (f.invoke(car()) == true) {
return cons(car(), {=>cdr().filter(f)});
} else {
return cdr().filter(f);
}
}
return null;
}
// factory method cons
public static <E> LazyStream<E> cons(E val, {=>Stream<E>} c) {
return new LazyStream<E>(val, c);
}
}
}
A couple of points bugging ..
I had to make up the
Unary class since the closure did not allow me to specify ? super E in the left hand side. Ricky has clarified with Neal that this is due to the fact that things on the left hand side of a closure automatically have ? super in their types. Hence a little noise ..static class Unary<T,R> {
private {T=>R} u;
public Unary({T=>R} u) {
this.u = u;
}
public R invoke(T arg) {
return u.invoke(arg);
}
}
and now some tests ..
class StreamTest {
//.. all above stuff
//.. and the tests
// helper function generating sequence of natural numbers
static LazyStream<Integer> integersFrom(final int start) {
return LazyStream.cons(start, {=>integersFrom(start+1)});
}
// helper function for generating fibonacci sequence
static LazyStream<Integer> fibonacci(final int a, final int b) {
return LazyStream.cons(a, {=>fibonacci(b, a+b)});
}
public static void main(String[] args) {
// natural numbers
Stream<Integer> integers = integersFrom(0);
Stream<Integer> s = integers;
for(int i=0; i<20; i++) {
System.out.print(s.car() + " ");
s = s.cdr();
}
System.out.println("...");
// a map example over the stream
Stream<Integer> t = integers;
Stream<Integer> u = t.map(new Unary<Integer, Integer>({Integer i=>i*i}));
for(int i=0; i<20; i++) {
System.out.print(u.car() + " ");
u = u.cdr();
}
System.out.println("...");
// a filter over stream
Stream<Integer> x = integers;
Stream<Integer> y = x.filter(new Unary<Integer, Boolean>({Integer i=>i%2==0}));
for(int i=0; i<20; i++) {
System.out.print(y.car() + " ");
y = y.cdr();
}
System.out.println("...");
}
}
Closures in Java will surely bring in a new paradigm of programming within the developers. The amount of excitement that the prototype has already generated is phenomenal. It'll be too bad if they do not appear in Java 7.
Update: Ricky Clarkson points out in the Comments that
{? super E=>? extends R} is the same as {E=>R}. The covariance / contravariance stuff just blew off my mind when I compiled the post. Hence the Unary class is not required. Just remove the class and substitute the closure in map() and filter(). e.g.public <R> Stream<R> map({E=>R} f) {
return cons(f.invoke(car), {=>cdr().map(f)});
}
