Skip to content

Commit 777949b

Browse files
jnapejnape
committed
Adding IterateT#runStep for supporting interleaving semantics
1 parent 86743e0 commit 777949b

File tree

3 files changed

+69
-11
lines changed

3 files changed

+69
-11
lines changed

‎CHANGELOG.md

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,10 @@ The format is based on [Keep a Changelog](http://keepachangelog.com/).
55

66
## [Unreleased]
77

8-
There are currently no unreleased changes.
8+
### Added
9+
10+
- `IterateT#runStep`, a method used to run a single step of an IterateT without the contractual
11+
guarantee of emitting a value or reaching the end
912

1013
## [5.3.0] - 2020-12-07
1114

‎src/main/java/com/jnape/palatable/lambda/monad/transformer/builtin/IterateT.java

Lines changed: 29 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -65,8 +65,7 @@
6565
* @param <M> the effect type
6666
* @param <A> the element type
6767
*/
68-
public class IterateT<M extends MonadRec<?, M>, A> implements
69-
MonadT<M, A, IterateT<M, ?>, IterateT<?, ?>> {
68+
public class IterateT<M extends MonadRec<?, M>, A> implements MonadT<M, A, IterateT<M, ?>, IterateT<?, ?>> {
7069

7170
private final Pure<M> pureM;
7271
private final ImmutableQueue<Choice2<Fn0<MonadRec<Maybe<Tuple2<A, IterateT<M, A>>>, M>>, MonadRec<A, M>>> spine;
@@ -84,15 +83,35 @@ private IterateT(Pure<M> pureM,
8483
* @return the embedded {@link Monad}
8584
*/
8685
public <MMTA extends MonadRec<Maybe<Tuple2<A, IterateT<M, A>>>, M>> MMTA runIterateT() {
87-
MonadRec<ImmutableQueue<Choice2<Fn0<MonadRec<Maybe<Tuple2<A, IterateT<M, A>>>, M>>, MonadRec<A, M>>>, M>
88-
mSpine = pureM.apply(spine);
89-
return mSpine.trampolineM(tSpine -> tSpine.head().<MonadRec<RecursiveResult<ImmutableQueue<Choice2<Fn0<MonadRec<Maybe<Tuple2<A, IterateT<M, A>>>, M>>, MonadRec<A, M>>>, Maybe<Tuple2<A, IterateT<M, A>>>>, M>>match(
90-
___ -> pureM.apply(terminate(nothing())),
86+
return pureM.<IterateT<M, A>, MonadRec<IterateT<M, A>, M>>apply(this)
87+
.<Maybe<Tuple2<A, IterateT<M, A>>>>trampolineM(iterateT -> iterateT.runStep()
88+
.fmap(maybeMore -> maybeMore.match(
89+
fn0(() -> terminate(nothing())),
90+
t -> t.into((Maybe<A> maybeA, IterateT<M, A> as) -> maybeA.match(
91+
fn0(() -> recurse(as)),
92+
a -> terminate(just(tuple(a, as))))))))
93+
.coerce();
94+
}
95+
96+
/**
97+
* Run a single step of this {@link IterateT}, where a step is the smallest amount of work that could possibly be
98+
* productive in advancing through the {@link IterateT}. Useful for implementing interleaving algorithms that
99+
* require {@link IterateT IterateTs} to yield, emit, or terminate as soon as possible, regardless of whether the
100+
* next element is readily available.
101+
*
102+
* @param <MStep> the witnessed target type of the step
103+
* @return the step
104+
*/
105+
public <MStep extends MonadRec<Maybe<Tuple2<Maybe<A>, IterateT<M, A>>>, M>> MStep runStep() {
106+
return spine.head().match(
107+
fn0(() -> pureM.<Maybe<Tuple2<Maybe<A>, IterateT<M, A>>>, MStep>apply(nothing())),
91108
thunkOrReal -> thunkOrReal.match(
92-
thunk -> thunk.apply().fmap(m -> m.match(
93-
___ -> recurse(tSpine.tail()),
94-
t -> terminate(just(t.fmap(as -> new IterateT<>(pureM, as.spine.concat(tSpine.tail()))))))),
95-
real -> real.fmap(a -> terminate(just(tuple(a, new IterateT<>(pureM, tSpine.tail())))))))).coerce();
109+
thunk -> thunk.apply().<Maybe<Tuple2<Maybe<A>, IterateT<M, A>>>>fmap(m -> m.match(
110+
fn0(() -> just(tuple(nothing(), new IterateT<>(pureM, spine.tail())))),
111+
t -> just(t.biMap(Maybe::just,
112+
as -> new IterateT<>(pureM, as.spine.concat(spine.tail()))))))
113+
.coerce(),
114+
ma -> ma.fmap(a -> just(tuple(just(a), new IterateT<>(pureM, spine.tail())))).coerce()));
96115
}
97116

98117
/**

‎src/test/java/com/jnape/palatable/lambda/monad/transformer/builtin/IterateTTest.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,7 @@
4848
import static com.jnape.palatable.lambda.monad.transformer.builtin.IterateT.of;
4949
import static com.jnape.palatable.lambda.monad.transformer.builtin.IterateT.pureIterateT;
5050
import static com.jnape.palatable.lambda.monad.transformer.builtin.IterateT.singleton;
51+
import static com.jnape.palatable.lambda.monad.transformer.builtin.IterateT.suspended;
5152
import static com.jnape.palatable.lambda.monad.transformer.builtin.IterateT.unfold;
5253
import static com.jnape.palatable.lambda.monoid.builtin.AddAll.addAll;
5354
import static com.jnape.palatable.lambda.monoid.builtin.Join.join;
@@ -313,4 +314,39 @@ public void flatMapCostsNoMoreEffortThanRequiredToYieldFirstValue() {
313314
assertEquals(1, flatMapCost.get());
314315
assertEquals(1, unfoldCost.get());
315316
}
317+
318+
@Test
319+
public void runStep() {
320+
assertEquals(new Identity<>(nothing()),
321+
IterateT.<Identity<?>, Integer>empty(pureIdentity())
322+
.<Identity<Maybe<Tuple2<Maybe<Integer>, IterateT<Identity<?>, Integer>>>>>runStep());
323+
324+
Tuple2<Maybe<Integer>, IterateT<Identity<?>, Integer>> singletonStep =
325+
singleton(new Identity<>(1))
326+
.<Identity<Maybe<Tuple2<Maybe<Integer>, IterateT<Identity<?>, Integer>>>>>runStep()
327+
.runIdentity()
328+
.orElseThrow(AssertionError::new);
329+
assertEquals(just(1), singletonStep._1());
330+
assertThat(singletonStep._2(), isEmpty());
331+
332+
Tuple2<Maybe<Integer>, IterateT<Identity<?>, Integer>> emptySuspendedStep =
333+
IterateT.<Identity<?>, Integer>suspended(() -> new Identity<>(nothing()),
334+
pureIdentity())
335+
.<Identity<Maybe<Tuple2<Maybe<Integer>, IterateT<Identity<?>, Integer>>>>>runStep()
336+
.runIdentity()
337+
.orElseThrow(AssertionError::new);
338+
339+
assertEquals(nothing(), emptySuspendedStep._1());
340+
assertThat(emptySuspendedStep._2(), isEmpty());
341+
342+
Tuple2<Maybe<Integer>, IterateT<Identity<?>, Integer>> nonEmptySuspendedStep =
343+
suspended(() -> new Identity<>(just(tuple(1, empty(pureIdentity())))),
344+
pureIdentity())
345+
.<Identity<Maybe<Tuple2<Maybe<Integer>, IterateT<Identity<?>, Integer>>>>>runStep()
346+
.runIdentity()
347+
.orElseThrow(AssertionError::new);
348+
349+
assertEquals(just(1), nonEmptySuspendedStep._1());
350+
assertThat(nonEmptySuspendedStep._2(), isEmpty());
351+
}
316352
}

0 commit comments

Comments
 (0)