- Snoc deforesting moved to custom Iterable

jnape · jnape · commit db06c1995eae · 2018-02-19T16:27:07.000-06:00
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -11,7 +11,7 @@ The format is based on [Keep a Changelog](http://keepachangelog.com/).
 - `Identity`, `Compose`, and `Const` functors all have better `toString` implementations
 - `Into3-8` now supports functions with parameter variance
 - `HListLens#tail` is now covariant in `Tail` parameter
-- More functions now automatically deforest nested calls
+- More functions now automatically deforest nested calls (`drop`, `snoc`)
 
 ### Added
 - `BoundedBifunctor`, a `Bifunctor` super type that offers upper bounds for both parameters
diff --git a/src/main/java/com/jnape/palatable/lambda/functions/builtin/fn2/Snoc.java b/src/main/java/com/jnape/palatable/lambda/functions/builtin/fn2/Snoc.java
@@ -2,7 +2,7 @@
 
 import com.jnape.palatable.lambda.functions.Fn1;
 import com.jnape.palatable.lambda.functions.Fn2;
-import com.jnape.palatable.lambda.iteration.SnocIterator;
+import com.jnape.palatable.lambda.iteration.SnocIterable;
 
 /**
  * Opposite of {@link Cons}: lazily append an element to the end of the given {@link Iterable}.
@@ -22,7 +22,7 @@ private Snoc() {
 
     @Override
     public Iterable<A> apply(A a, Iterable<A> as) {
-        return () -> new SnocIterator<>(a, as);
+        return new SnocIterable<>(a, as);
     }
 
     @SuppressWarnings("unchecked")
diff --git a/src/main/java/com/jnape/palatable/lambda/iteration/DroppingIterable.java b/src/main/java/com/jnape/palatable/lambda/iteration/DroppingIterable.java
@@ -2,7 +2,7 @@
 
 import java.util.Iterator;
 
-public class DroppingIterable<A> implements Iterable<A> {
+public final class DroppingIterable<A> implements Iterable<A> {
     private final int         n;
     private final Iterable<A> as;
 
diff --git a/src/main/java/com/jnape/palatable/lambda/iteration/SnocIterable.java b/src/main/java/com/jnape/palatable/lambda/iteration/SnocIterable.java
@@ -0,0 +1,28 @@
+package com.jnape.palatable.lambda.iteration;
+
+import java.util.Collections;
+import java.util.Iterator;
+
+import static com.jnape.palatable.lambda.functions.builtin.fn2.Cons.cons;
+import static com.jnape.palatable.lambda.monoid.builtin.Concat.concat;
+
+public final class SnocIterable<A> implements Iterable<A> {
+    private final Iterable<A> as;
+    private final Iterable<A> snocs;
+
+    public SnocIterable(A a, Iterable<A> as) {
+        Iterable<A> snocs = cons(a, Collections::emptyIterator);
+        while (as instanceof SnocIterable) {
+            SnocIterable<A> nested = ((SnocIterable<A>) as);
+            as = nested.as;
+            snocs = concat(nested.snocs, snocs);
+        }
+        this.as = as;
+        this.snocs = snocs;
+    }
+
+    @Override
+    public Iterator<A> iterator() {
+        return new SnocIterator<>(as.iterator(), snocs.iterator());
+    }
+}
diff --git a/src/main/java/com/jnape/palatable/lambda/iteration/SnocIterator.java b/src/main/java/com/jnape/palatable/lambda/iteration/SnocIterator.java
@@ -1,48 +1,28 @@
 package com.jnape.palatable.lambda.iteration;
 
-import java.util.Collections;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
-import java.util.function.Supplier;
-
-import static com.jnape.palatable.lambda.functions.builtin.fn2.Cons.cons;
 
 public final class SnocIterator<A> implements Iterator<A> {
 
-    private final Supplier<Iterator<A>> initsSupplier;
-    private final A                     last;
-    private       Iterator<A>           inits;
-    private       Iterator<A>           lasts;
+    private final Iterator<A> as;
+    private final Iterator<A> snocs;
 
-    public SnocIterator(A last, Iterable<A> inits) {
-        this.last = last;
-        initsSupplier = inits::iterator;
+    public SnocIterator(Iterator<A> as, Iterator<A> snocs) {
+        this.as = as;
+        this.snocs = snocs;
     }
 
     @Override
     public boolean hasNext() {
-        if (inits == null)
-            queueAndDeforest();
-
-        return inits.hasNext() || lasts.hasNext();
+        return as.hasNext() || snocs.hasNext();
     }
 
     @Override
     public A next() {
         if (!hasNext())
             throw new NoSuchElementException();
 
-        return inits.hasNext() ? inits.next() : lasts.next();
-    }
-
-    private void queueAndDeforest() {
-        Iterable<A> lastConses = Collections::emptyIterator;
-        inits = this;
-        while (inits instanceof SnocIterator) {
-            SnocIterator<A> it = (SnocIterator<A>) inits;
-            lastConses = cons(it.last, lastConses);
-            inits = it.initsSupplier.get();
-        }
-        lasts = lastConses.iterator();
+        return as.hasNext() ? as.next() : snocs.next();
     }
 }
diff --git a/src/test/java/com/jnape/palatable/lambda/iteration/SnocIterableTest.java b/src/test/java/com/jnape/palatable/lambda/iteration/SnocIterableTest.java
@@ -0,0 +1,16 @@
+package com.jnape.palatable.lambda.iteration;
+
+import com.jnape.palatable.lambda.functions.Fn1;
+import com.jnape.palatable.traitor.annotations.TestTraits;
+import com.jnape.palatable.traitor.runners.Traits;
+import org.junit.runner.RunWith;
+import testsupport.traits.NestingStackSafety;
+
+@RunWith(Traits.class)
+public class SnocIterableTest {
+
+    @TestTraits({NestingStackSafety.class})
+    public Fn1<Iterable<Object>, Iterable<Object>> testSubject() {
+        return xs -> new SnocIterable<>(1, xs);
+    }
+}
diff --git a/src/test/java/com/jnape/palatable/lambda/iteration/SnocIteratorTest.java b/src/test/java/com/jnape/palatable/lambda/iteration/SnocIteratorTest.java
@@ -3,14 +3,8 @@
 import org.junit.Before;
 import org.junit.Test;
 
-import java.util.Collections;
-
-import static com.jnape.palatable.lambda.adt.Maybe.just;
-import static com.jnape.palatable.lambda.functions.builtin.fn1.Last.last;
-import static com.jnape.palatable.lambda.functions.builtin.fn2.Iterate.iterate;
-import static com.jnape.palatable.lambda.functions.builtin.fn2.Take.take;
-import static com.jnape.palatable.lambda.functions.builtin.fn3.FoldLeft.foldLeft;
 import static java.util.Arrays.asList;
+import static java.util.Collections.singletonList;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
@@ -21,7 +15,7 @@ public class SnocIteratorTest {
 
     @Before
     public void setUp() {
-        iterator = new SnocIterator<>(3, asList(1, 2));
+        iterator = new SnocIterator<>(asList(1, 2).iterator(), singletonList(3).iterator());
     }
 
     @Test
@@ -45,14 +39,4 @@ public void doesNotHaveNextIfLastIterated() {
         iterator.next();
         assertFalse(iterator.hasNext());
     }
-
-    @Test
-    public void stackSafety() {
-        int stackBlowingNumber = 100000;
-        Iterable<Integer> ints = foldLeft((xs, x) -> () -> new SnocIterator<>(x, xs),
-                                          Collections::emptyIterator,
-                                          take(stackBlowingNumber, iterate(x -> x + 1, 1)));
-
-        assertEquals(just(stackBlowingNumber), last(ints));
-    }
 }
