/* package whatever; // don't place package name! */

import java.util.ArrayList;
import java.util.function.BiFunction;
import java.util.function.Supplier;

class Ideone {

    public static void main(String[] args) {
        System.out.println(Lazy.forceList(Lazy.take(10, fibs())));
    }

    private static List<Integer> fibs() {
        return Lazy.cons(
                () -> 0,
                () -> Lazy.cons(
                        () -> 1,
                        () -> Lazy.zip(Integer::sum, fibs(), fibs().tail())));
    }
}

final class Promise<T> {

    private static final Object undefined = new Object();

    private final Supplier<T> delayedExpression;

    @SuppressWarnings("unchecked")
    private T value = (T) undefined;

    Promise(Supplier<T> expr) {
        this.delayedExpression = expr;
    }

    public T force() {
        if (value == undefined) {
            value = delayedExpression.get();
        }
        return value;
    }
}

final class List<T> {

    static final List<?> NIL = new List<>(null, null);

    private final Promise<T> head;
    private final Promise<List<T>> tail;

    List(Promise<T> head, Promise<List<T>> tail) {
        this.head = head;
        this.tail = tail;
    }

    public T head() {
        return head.force();
    }

    public List<T> tail() {
        return tail.force();
    }
}

final class Lazy {

    public static <T> Promise<T> delay(Supplier<T> expr) {
        return new Promise<>(expr);
    }

    public static <T> List<T> cons(Supplier<T> headExpr, Supplier<List<T>> tailExpr) {
        return new List<>(new Promise<>(headExpr), new Promise<>(tailExpr));
    }

    public static <T> List<T> nil() {
        @SuppressWarnings("unchecked")
        var nil = (List<T>) List.NIL;
        return nil;
    }

    public static <T> List<T> take(int n, List<T> xs) {
        if (n <= 0) {
            return nil();
        }
        if (xs == nil()) {
            return nil();
        }
        return cons(xs::head, () -> take(n - 1, xs.tail()));
    }

    public static <A, B, R> List<R> zip(BiFunction<A, B, R> f, List<A> xs, List<B> ys) {
        if (xs == nil()) {
            return nil();
        }
        if (ys == nil()) {
            return nil();
        }
        return cons(
                () -> f.apply(xs.head(), ys.head()),
                () -> zip(f, xs.tail(), ys.tail()));
    }

    public static <T> ArrayList<T> forceList(List<T> xs) {
        final var list = new ArrayList<T>();
        for (var it = xs; it != nil(); it = it.tail()) {
            list.add(it.head());
        }
        return list;
    }

    @SafeVarargs
    public static <T> List<T> list(Supplier<T>... values) {
        if (values == null || values.length == 0) {
            return nil();
        }
        return list(values, 0);
    }

    private static <T> List<T> list(Supplier<T>[] values, int headCursor) {
        if (headCursor == values.length) {
            return nil();
        }
        return new List<>(new Promise<>(values[headCursor]), new Promise<>(() -> list(values, headCursor+1)));
    }

    private Lazy() {
        throw new UnsupportedOperationException("utility class");
    }
}