fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.ArrayList;
  4. import java.util.function.BiFunction;
  5. import java.util.function.Supplier;
  6.  
  7. class Ideone {
  8.  
  9.     public static void main(String[] args) {
  10.         final var fibs = fibs();
  11.         System.out.println(Lazy.forceList(Lazy.take(10, fibs)));
  12.     }
  13.  
  14.     private static List<Integer> fibs() {
  15.         final var cell = new Cell<List<Integer>>();
  16.         cell.value = Lazy.cons(
  17.                 () -> 0,
  18.                 () -> Lazy.cons(
  19.                         () -> 1,
  20.                         () -> Lazy.zip(Integer::sum, cell.value, cell.value.tail())));
  21.         return cell.value;
  22.     }
  23. }
  24.  
  25. final class Cell<T> {
  26.  
  27.     T value;
  28. }
  29.  
  30. final class Promise<T> {
  31.  
  32.     private static final Object undefined = new Object();
  33.  
  34.     private final Supplier<T> delayedExpression;
  35.  
  36.     @SuppressWarnings("unchecked")
  37.     private T value = (T) undefined;
  38.  
  39.     Promise(Supplier<T> expr) {
  40.         this.delayedExpression = expr;
  41.     }
  42.  
  43.     public T force() {
  44.         if (value == undefined) {
  45.             value = delayedExpression.get();
  46.         }
  47.         return value;
  48.     }
  49. }
  50.  
  51. final class List<T> {
  52.  
  53.     static final List<?> NIL = new List<>(null, null);
  54.  
  55.     private final Promise<T> head;
  56.     private final Promise<List<T>> tail;
  57.  
  58.     List(Promise<T> head, Promise<List<T>> tail) {
  59.         this.head = head;
  60.         this.tail = tail;
  61.     }
  62.  
  63.     public T head() {
  64.         return head.force();
  65.     }
  66.  
  67.     public List<T> tail() {
  68.         return tail.force();
  69.     }
  70. }
  71.  
  72. final class Lazy {
  73.  
  74.     public static <T> Promise<T> delay(Supplier<T> expr) {
  75.         return new Promise<>(expr);
  76.     }
  77.  
  78.     public static <T> List<T> cons(Supplier<T> headExpr, Supplier<List<T>> tailExpr) {
  79.         return new List<>(new Promise<>(headExpr), new Promise<>(tailExpr));
  80.     }
  81.  
  82.     public static <T> List<T> nil() {
  83.         @SuppressWarnings("unchecked")
  84.         var nil = (List<T>) List.NIL;
  85.         return nil;
  86.     }
  87.  
  88.     public static <T> List<T> take(int n, List<T> xs) {
  89.         if (n <= 0) {
  90.             return nil();
  91.         }
  92.         if (xs == nil()) {
  93.             return nil();
  94.         }
  95.         return cons(xs::head, () -> take(n - 1, xs.tail()));
  96.     }
  97.  
  98.     public static <A, B, R> List<R> zip(BiFunction<A, B, R> f, List<A> xs, List<B> ys) {
  99.         if (xs == nil()) {
  100.             return nil();
  101.         }
  102.         if (ys == nil()) {
  103.             return nil();
  104.         }
  105.         return cons(
  106.                 () -> f.apply(xs.head(), ys.head()),
  107.                 () -> zip(f, xs.tail(), ys.tail()));
  108.     }
  109.  
  110.     public static <T> ArrayList<T> forceList(List<T> xs) {
  111.         final var list = new ArrayList<T>();
  112.         for (var it = xs; it != nil(); it = it.tail()) {
  113.             list.add(it.head());
  114.         }
  115.         return list;
  116.     }
  117.  
  118.     @SafeVarargs
  119.     public static <T> List<T> list(Supplier<T>... values) {
  120.         if (values == null || values.length == 0) {
  121.             return nil();
  122.         }
  123.         return list(values, 0);
  124.     }
  125.  
  126.     private static <T> List<T> list(Supplier<T>[] values, int headCursor) {
  127.         if (headCursor == values.length) {
  128.             return nil();
  129.         }
  130.         return new List<>(new Promise<>(values[headCursor]), new Promise<>(() -> list(values, headCursor+1)));
  131.     }
  132.  
  133.     private Lazy() {
  134.         throw new UnsupportedOperationException("utility class");
  135.     }
  136. }
  137.  
Success #stdin #stdout 0.08s 48292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
https://ideone.com/K4Z9QW
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!