Skip to content

Instantly share code, notes, and snippets.

@lenalebt
Last active October 21, 2017 07:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lenalebt/e627e13d034011ac156d44917fe466d3 to your computer and use it in GitHub Desktop.
Save lenalebt/e627e13d034011ac156d44917fe466d3 to your computer and use it in GitHub Desktop.
Lazy Fibonacci in Java!
package de.lenabrueder;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;
import java.util.function.Supplier;
public class LazyList<T> {
final T head;
LazyList<T> tail = null;
Supplier<LazyList<T>> tailSupplier;
public LazyList(T head, Supplier<LazyList<T>> tail) {
this.head = head;
this.tailSupplier = tail;
}
public T getHead() {
return head;
}
public <B> LazyList<Pair<T,B>> zip(LazyList<B> b) {
return new LazyList<Pair<T, B>>(new Pair<T,B>(this.head, b.head), () -> this.getTail().zip(b.getTail()));
}
public <B> LazyList<B> map(Function<T,B> f) {
return new LazyList<B>(f.apply(this.head), () -> this.getTail().map(f));
}
public List<T> take(int n) {
List<T> list = new ArrayList<>(n);
LazyList<T> el = this;
for (int i=0; i<n; i++) {
list.add(el.head);
el = el.getTail();
}
return list;
}
public void setTail(Supplier<LazyList<T>> tail) {
this.tailSupplier = tail;
}
public LazyList<T> getTail() {
if (tail == null) {
tail = tailSupplier.get();
tailSupplier = null;
}
return tail;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(head.toString());
LazyList<T> _tail = tail;
while (_tail != null) {
sb.append(", ");
sb.append(_tail.getHead());
_tail = _tail.tail;
}
return sb.toString();
}
}
package de.lenabrueder;
import java.util.List;
public class Main {
public static void main(String[] args) {
LazyList<Long> fibs = new LazyList<>(0L,
() -> new LazyList<>(1L,
null //TODO: workaround for "not initialized" and "effectively-final", see below
)
);
fibs.getTail().setTail(() -> fibs.zip(fibs.getTail()).map(p -> p.getA() + p.getB()));
List<Long> realFibs = fibs.take(20);
System.out.println(realFibs);
}
}
package de.lenabrueder;
public class Pair<A,B> {
A a;
B b;
public Pair(A a, B b) {
this.a = a;
this.b = b;
}
public A getA() {
return a;
}
public B getB() {
return b;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment