Skip to content

Commit f01e118

Browse files
jnapejnape
committed
Concat is now stack-safe on both paths of nesting
1 parent 1c63de8 commit f01e118

File tree

8 files changed

+268
-149
lines changed

8 files changed

+268
-149
lines changed

‎CHANGELOG.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ The format is based on [Keep a Changelog](http://keepachangelog.com/).
1111
- `Identity`, `Compose`, and `Const` functors all have better `toString` implementations
1212
- `Into3-8` now supports functions with parameter variance
1313
- `HListLens#tail` is now covariant in `Tail` parameter
14-
- More functions now automatically deforest nested calls (`cons`, `cycle`, `distinct`, `drop`, `dropwhile`, `filter`, `map`, `reverse`, `snoc`, `take`, `takewhile`, `tail`)
14+
- More functions now automatically deforest nested calls (`concat` `cons`, `cycle`, `distinct`, `drop`, `dropwhile`, `filter`, `map`, `reverse`, `snoc`, `take`, `takewhile`, `tail`)
1515

1616
### Added
1717
- `BoundedBifunctor`, a `Bifunctor` super type that offers upper bounds for both parameters

‎src/main/java/com/jnape/palatable/lambda/iteration/ConcatenatingIterable.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package com.jnape.palatable.lambda.iteration;
2+
3+
import java.util.Iterator;
4+
5+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Flatten.flatten;
6+
7+
public final class ConcatenatingIterable<A> implements Iterable<A> {
8+
9+
private final ImmutableQueue<Iterable<A>> iterables;
10+
11+
public ConcatenatingIterable(Iterable<A> xs, Iterable<A> ys) {
12+
if (xs instanceof ConcatenatingIterable) {
13+
ImmutableQueue<Iterable<A>> iterables = ((ConcatenatingIterable<A>) xs).iterables;
14+
this.iterables = ys instanceof ConcatenatingIterable
15+
? iterables.concat(((ConcatenatingIterable<A>) ys).iterables)
16+
: iterables.pushBack(ys);
17+
} else {
18+
iterables = ys instanceof ConcatenatingIterable
19+
? ((ConcatenatingIterable<A>) ys).iterables.pushFront(xs)
20+
: ImmutableQueue.<Iterable<A>>empty().pushFront(ys).pushFront(xs);
21+
}
22+
}
23+
24+
@Override
25+
public Iterator<A> iterator() {
26+
return flatten(iterables).iterator();
27+
}
28+
}

‎src/main/java/com/jnape/palatable/lambda/iteration/ConcatenatingIterator.java

Lines changed: 0 additions & 47 deletions
This file was deleted.

‎src/main/java/com/jnape/palatable/lambda/iteration/ImmutableQueue.java

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
package com.jnape.palatable.lambda.iteration;
2+
3+
import com.jnape.palatable.lambda.adt.Maybe;
4+
5+
import java.util.Iterator;
6+
import java.util.NoSuchElementException;
7+
8+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Constantly.constantly;
9+
import static com.jnape.palatable.lambda.functions.builtin.fn3.FoldLeft.foldLeft;
10+
11+
abstract class ImmutableQueue<A> implements Iterable<A> {
12+
13+
abstract ImmutableQueue<A> pushFront(A a);
14+
15+
abstract ImmutableQueue<A> pushBack(A a);
16+
17+
abstract Maybe<A> head();
18+
19+
abstract ImmutableQueue<A> tail();
20+
21+
abstract ImmutableQueue<A> concat(ImmutableQueue<A> other);
22+
23+
final boolean isEmpty() {
24+
return head().fmap(constantly(false)).orElse(true);
25+
}
26+
27+
@Override
28+
public Iterator<A> iterator() {
29+
return new Iterator<A>() {
30+
private ImmutableQueue<A> queue = ImmutableQueue.this;
31+
32+
@Override
33+
public boolean hasNext() {
34+
return !queue.isEmpty();
35+
}
36+
37+
@Override
38+
public A next() {
39+
A next = queue.head().orElseThrow(NoSuchElementException::new);
40+
queue = queue.tail();
41+
return next;
42+
}
43+
};
44+
}
45+
46+
@SuppressWarnings("unchecked")
47+
public static <A> ImmutableQueue<A> empty() {
48+
return Empty.INSTANCE;
49+
}
50+
51+
private static final class Empty<A> extends ImmutableQueue<A> {
52+
private static final Empty INSTANCE = new Empty();
53+
54+
@Override
55+
ImmutableQueue<A> pushFront(A a) {
56+
return new NonEmpty<>(ImmutableStack.<A>empty().push(a), ImmutableStack.empty());
57+
}
58+
59+
@Override
60+
ImmutableQueue<A> pushBack(A a) {
61+
return pushFront(a);
62+
}
63+
64+
@Override
65+
ImmutableQueue<A> concat(ImmutableQueue<A> other) {
66+
return other;
67+
}
68+
69+
@Override
70+
Maybe<A> head() {
71+
return Maybe.nothing();
72+
}
73+
74+
@Override
75+
ImmutableQueue<A> tail() {
76+
return this;
77+
}
78+
}
79+
80+
private static final class NonEmpty<A> extends ImmutableQueue<A> {
81+
private final ImmutableStack<A> outbound;
82+
private final ImmutableStack<A> inbound;
83+
84+
private NonEmpty(ImmutableStack<A> outbound, ImmutableStack<A> inbound) {
85+
this.outbound = outbound;
86+
this.inbound = inbound;
87+
}
88+
89+
@Override
90+
ImmutableQueue<A> pushFront(A a) {
91+
return new NonEmpty<>(outbound.push(a), inbound);
92+
}
93+
94+
@Override
95+
ImmutableQueue<A> pushBack(A a) {
96+
return new NonEmpty<>(outbound, inbound.push(a));
97+
}
98+
99+
@Override
100+
ImmutableQueue<A> concat(ImmutableQueue<A> other) {
101+
return new NonEmpty<>(outbound, foldLeft(ImmutableStack::push, inbound, other));
102+
}
103+
104+
@Override
105+
Maybe<A> head() {
106+
return outbound.head();
107+
}
108+
109+
@Override
110+
ImmutableQueue<A> tail() {
111+
ImmutableStack<A> outTail = outbound.tail();
112+
if (!outTail.isEmpty())
113+
return new NonEmpty<>(outTail, inbound);
114+
115+
ImmutableStack<A> newOutbound = foldLeft(ImmutableStack::push, ImmutableStack.<A>empty(), inbound);
116+
return newOutbound.isEmpty() ? empty() : new NonEmpty<>(newOutbound, ImmutableStack.empty());
117+
}
118+
}
119+
}

‎src/main/java/com/jnape/palatable/lambda/iteration/ImmutableStack.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package com.jnape.palatable.lambda.iteration;
2+
3+
import com.jnape.palatable.lambda.adt.Maybe;
4+
5+
import java.util.Iterator;
6+
import java.util.NoSuchElementException;
7+
8+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Constantly.constantly;
9+
10+
abstract class ImmutableStack<A> implements Iterable<A> {
11+
12+
final ImmutableStack<A> push(A a) {
13+
return new Node<>(a, this);
14+
}
15+
16+
abstract Maybe<A> head();
17+
18+
abstract ImmutableStack<A> tail();
19+
20+
final boolean isEmpty() {
21+
return head().fmap(constantly(false)).orElse(true);
22+
}
23+
24+
@Override
25+
public Iterator<A> iterator() {
26+
return new Iterator<A>() {
27+
private ImmutableStack<A> stack = ImmutableStack.this;
28+
29+
@Override
30+
public boolean hasNext() {
31+
return !stack.isEmpty();
32+
}
33+
34+
@Override
35+
public A next() {
36+
A next = stack.head().orElseThrow(NoSuchElementException::new);
37+
stack = stack.tail();
38+
return next;
39+
}
40+
};
41+
}
42+
43+
@SuppressWarnings("unchecked")
44+
public static <A> ImmutableStack<A> empty() {
45+
return Empty.INSTANCE;
46+
}
47+
48+
private static final class Empty<A> extends ImmutableStack<A> {
49+
private static final Empty INSTANCE = new Empty();
50+
51+
@Override
52+
Maybe<A> head() {
53+
return Maybe.nothing();
54+
}
55+
56+
@Override
57+
ImmutableStack<A> tail() {
58+
return this;
59+
}
60+
}
61+
62+
private static final class Node<A> extends ImmutableStack<A> {
63+
private final A head;
64+
private final ImmutableStack<A> tail;
65+
66+
public Node(A head, ImmutableStack<A> tail) {
67+
this.head = head;
68+
this.tail = tail;
69+
}
70+
71+
@Override
72+
Maybe<A> head() {
73+
return Maybe.just(head);
74+
}
75+
76+
@Override
77+
ImmutableStack<A> tail() {
78+
return tail;
79+
}
80+
}
81+
}

‎src/main/java/com/jnape/palatable/lambda/monoid/builtin/Concat.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
package com.jnape.palatable.lambda.monoid.builtin;
22

33
import com.jnape.palatable.lambda.functions.Fn1;
4-
import com.jnape.palatable.lambda.iteration.ConcatenatingIterator;
4+
import com.jnape.palatable.lambda.iteration.ConcatenatingIterable;
55
import com.jnape.palatable.lambda.monoid.Monoid;
66

77
import java.util.Collections;
@@ -25,7 +25,7 @@ public Iterable<A> identity() {
2525

2626
@Override
2727
public Iterable<A> apply(Iterable<A> xs, Iterable<A> ys) {
28-
return () -> new ConcatenatingIterator<>(xs, ys);
28+
return new ConcatenatingIterable<>(xs, ys);
2929
}
3030

3131
@SuppressWarnings("unchecked")

‎src/test/java/com/jnape/palatable/lambda/iteration/ConcatenatingIterableTest.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.jnape.palatable.lambda.iteration;
2+
3+
import com.jnape.palatable.lambda.functions.Fn1;
4+
import com.jnape.palatable.lambda.monoid.builtin.Concat;
5+
import com.jnape.palatable.traitor.annotations.TestTraits;
6+
import com.jnape.palatable.traitor.framework.Subjects;
7+
import com.jnape.palatable.traitor.runners.Traits;
8+
import org.junit.Test;
9+
import org.junit.runner.RunWith;
10+
import testsupport.traits.Deforesting;
11+
12+
import static com.jnape.palatable.lambda.adt.Maybe.just;
13+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Last.last;
14+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Repeat.repeat;
15+
import static com.jnape.palatable.lambda.functions.builtin.fn2.Replicate.replicate;
16+
import static com.jnape.palatable.traitor.framework.Subjects.subjects;
17+
import static java.util.Arrays.asList;
18+
import static java.util.Collections.emptyList;
19+
import static org.junit.Assert.assertEquals;
20+
21+
@RunWith(Traits.class)
22+
public class ConcatenatingIterableTest {
23+
24+
@TestTraits({Deforesting.class})
25+
public Subjects<Fn1<Iterable<Integer>, Iterable<Integer>>> testSubject() {
26+
return subjects(xs -> new ConcatenatingIterable<>(emptyList(), xs),
27+
xs -> new ConcatenatingIterable<>(xs, emptyList()),
28+
xs -> new ConcatenatingIterable<>(repeat(1), xs),
29+
xs -> new ConcatenatingIterable<>(xs, repeat(1)));
30+
}
31+
32+
@Test
33+
public void stackSafety() {
34+
Iterable<Integer> xs = Concat.<Integer>concat().reduceLeft(replicate(1_000_000, asList(1, 2, 3)));
35+
assertEquals(just(3), last(xs));
36+
}
37+
}

0 commit comments

Comments
 (0)