Skip to content

Commit 09e65d4

Browse files
runaroramarunarorama
committed
2 parents def75a1 + 700f689 commit 09e65d4

File tree

1 file changed

+259
-0
lines changed

1 file changed

+259
-0
lines changed

‎core/src/main/java/fj/control/Trampoline.java‎

Lines changed: 259 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,259 @@
1+
package fj.control;
2+
3+
import fj.F;
4+
import fj.P1;
5+
import fj.data.Either;
6+
7+
import static fj.data.Either.left;
8+
import static fj.data.Either.right;
9+
10+
/**
11+
* A Trampoline is a potentially branching computation that can be stepped through and executed in constant stack.
12+
*/
13+
public abstract class Trampoline<A> {
14+
private static abstract class Normal<A> extends Trampoline<A> {
15+
public abstract <R> R foldNormal(final F<A, R> pure, final F<P1<Trampoline<A>>, R> k);
16+
17+
public <B> Trampoline<B> bind(final F<A, Trampoline<B>> f) {
18+
return codense(this, f);
19+
}
20+
}
21+
22+
private static final class Codense<A> extends Trampoline<A> {
23+
private final Normal<Object> sub;
24+
private final F<Object, Trampoline<A>> cont;
25+
26+
private Codense(final Normal<Object> t, final F<Object, Trampoline<A>> k) {
27+
sub = t;
28+
cont = k;
29+
}
30+
31+
public <R> R fold(final F<Normal<A>, R> n,
32+
final F<Codense<A>, R> gs) {
33+
return gs.f(this);
34+
}
35+
36+
public <B> Trampoline<B> bind(final F<A, Trampoline<B>> f) {
37+
return codense(sub, new F<Object, Trampoline<B>>() {
38+
public Trampoline<B> f(final Object o) {
39+
return suspend(new P1<Trampoline<B>>() {
40+
public Trampoline<B> _1() {
41+
return cont.f(o).bind(f);
42+
}
43+
});
44+
}
45+
});
46+
}
47+
48+
public Either<P1<Trampoline<A>>, A> resume() {
49+
return left(sub.resume().either(new F<P1<Trampoline<Object>>, P1<Trampoline<A>>>() {
50+
public P1<Trampoline<A>> f(final P1<Trampoline<Object>> p) {
51+
return p.map(new F<Trampoline<Object>, Trampoline<A>>() {
52+
public Trampoline<A> f(final Trampoline<Object> ot) {
53+
return ot.fold(new F<Normal<Object>, Trampoline<A>>() {
54+
public Trampoline<A> f(final Normal<Object> o) {
55+
return o.foldNormal(new F<Object, Trampoline<A>>() {
56+
public Trampoline<A> f(final Object o) {
57+
return cont.f(o);
58+
}
59+
}, new F<P1<Trampoline<Object>>, Trampoline<A>>() {
60+
public Trampoline<A> f(final P1<Trampoline<Object>> t) {
61+
return t._1().bind(cont);
62+
}
63+
}
64+
);
65+
}
66+
}, new F<Codense<Object>, Trampoline<A>>() {
67+
public Trampoline<A> f(final Codense<Object> c) {
68+
return codense(c.sub, new F<Object, Trampoline<A>>() {
69+
public Trampoline<A> f(final Object o) {
70+
return c.cont.f(o).bind(cont);
71+
}
72+
});
73+
}
74+
}
75+
);
76+
}
77+
});
78+
}
79+
}, new F<Object, P1<Trampoline<A>>>() {
80+
public P1<Trampoline<A>> f(final Object o) {
81+
return new P1<Trampoline<A>>() {
82+
public Trampoline<A> _1() {
83+
return cont.f(o);
84+
}
85+
};
86+
}
87+
}
88+
));
89+
}
90+
}
91+
92+
private static final class Suspend<A> extends Normal<A> {
93+
private final P1<Trampoline<A>> suspension;
94+
95+
private Suspend(final P1<Trampoline<A>> s) {
96+
suspension = s;
97+
}
98+
99+
public <R> R foldNormal(final F<A, R> pure, final F<P1<Trampoline<A>>, R> k) {
100+
return k.f(suspension);
101+
}
102+
103+
public <R> R fold(final F<Normal<A>, R> n, final F<Codense<A>, R> gs) {
104+
return n.f(this);
105+
}
106+
107+
public Either<P1<Trampoline<A>>, A> resume() {
108+
return left(suspension);
109+
}
110+
}
111+
112+
private static final class Pure<A> extends Normal<A> {
113+
private final A value;
114+
115+
private Pure(final A a) {
116+
value = a;
117+
}
118+
119+
public <R> R foldNormal(final F<A, R> pure, final F<P1<Trampoline<A>>, R> k) {
120+
return pure.f(value);
121+
}
122+
123+
public <R> R fold(final F<Normal<A>, R> n, final F<Codense<A>, R> gs) {
124+
return n.f(this);
125+
}
126+
127+
public Either<P1<Trampoline<A>>, A> resume() {
128+
return right(value);
129+
}
130+
}
131+
132+
@SuppressWarnings("unchecked")
133+
protected static <A, B> Codense<B> codense(final Normal<A> a, final F<A, Trampoline<B>> k) {
134+
return new Codense<B>((Normal<Object>) a, (F<Object, Trampoline<B>>) k);
135+
}
136+
137+
/**
138+
* @return The first-class version of `pure`.
139+
*/
140+
public static <A> F<A, Trampoline<A>> pure() {
141+
return new F<A, Trampoline<A>>() {
142+
public Trampoline<A> f(final A a) {
143+
return pure(a);
144+
}
145+
};
146+
}
147+
148+
/**
149+
* Constructs a leaf computation that results in the given value.
150+
* @param a The value of the result.
151+
* @return A trampoline that results in the given value.
152+
*/
153+
public static <A> Trampoline<A> pure(final A a) {
154+
return new Pure<A>(a);
155+
}
156+
157+
/**
158+
* Suspends the given computation in a thunk.
159+
* @param a A trampoline suspended in a thunk.
160+
* @return A trampoline whose next step runs the given thunk.
161+
*/
162+
public static <A> Trampoline<A> suspend(final P1<Trampoline<A>> a) {
163+
return new Suspend<A>(a);
164+
}
165+
166+
/**
167+
* @return The first-class version of `suspend`.
168+
*/
169+
public static <A> F<P1<Trampoline<A>>, Trampoline<A>> suspend_() {
170+
return new F<P1<Trampoline<A>>, Trampoline<A>>() {
171+
public Trampoline<A> f(final P1<Trampoline<A>> trampolineP1) {
172+
return suspend(trampolineP1);
173+
}
174+
};
175+
}
176+
177+
protected abstract <R> R fold(final F<Normal<A>, R> n, final F<Codense<A>, R> gs);
178+
179+
/**
180+
* Binds the given continuation to the result of this trampoline.
181+
* @param f A function that constructs a trampoline from the result of this trampoline.
182+
* @return A new trampoline that runs this trampoline, then continues with the given function.
183+
*/
184+
public abstract <B> Trampoline<B> bind(final F<A, Trampoline<B>> f);
185+
186+
/**
187+
* Maps the given function across the result of this trampoline. Monadic bind.
188+
* @param f A function that gets applied to the result of this trampoline.
189+
* @return A new trampoline that runs this trampoline, then applies the given function to the result.
190+
*/
191+
public final <B> Trampoline<B> map(final F<A, B> f) {
192+
return bind(Trampoline.<B>pure().o(f));
193+
}
194+
195+
/**
196+
* @return The first-class version of `bind`.
197+
*/
198+
public static <A, B> F<F<A, Trampoline<B>>, F<Trampoline<A>, Trampoline<B>>> bind_() {
199+
return new F<F<A, Trampoline<B>>, F<Trampoline<A>, Trampoline<B>>>() {
200+
public F<Trampoline<A>, Trampoline<B>> f(final F<A, Trampoline<B>> f) {
201+
return new F<Trampoline<A>, Trampoline<B>>() {
202+
public Trampoline<B> f(final Trampoline<A> a) {
203+
return a.bind(f);
204+
}
205+
};
206+
}
207+
};
208+
}
209+
210+
/**
211+
* @return The first-class version of `map`.
212+
*/
213+
public static <A, B> F<F<A, B>, F<Trampoline<A>, Trampoline<B>>> map_() {
214+
return new F<F<A, B>, F<Trampoline<A>, Trampoline<B>>>() {
215+
public F<Trampoline<A>, Trampoline<B>> f(final F<A, B> f) {
216+
return new F<Trampoline<A>, Trampoline<B>>() {
217+
public Trampoline<B> f(final Trampoline<A> a) {
218+
return a.map(f);
219+
}
220+
};
221+
}
222+
};
223+
}
224+
225+
/**
226+
* @return The first-class version of `resume`.
227+
*/
228+
public static <A> F<Trampoline<A>, Either<P1<Trampoline<A>>, A>> resume_() {
229+
return new F<Trampoline<A>, Either<P1<Trampoline<A>>, A>>() {
230+
public Either<P1<Trampoline<A>>, A> f(final Trampoline<A> aTrampoline) {
231+
return aTrampoline.resume();
232+
}
233+
};
234+
}
235+
236+
/**
237+
* Runs a single step of this computation.
238+
* @return The next step of this compuation.
239+
*/
240+
public abstract Either<P1<Trampoline<A>>, A> resume();
241+
242+
/**
243+
* Runs this computation all the way to the end, in constant stack.
244+
* @return The end result of this computation.
245+
*/
246+
@SuppressWarnings("LoopStatementThatDoesntLoop")
247+
public A run() {
248+
Trampoline<A> current = this;
249+
while (true) {
250+
final Either<P1<Trampoline<A>>, A> x = current.resume();
251+
for (final P1<Trampoline<A>> t: x.left()) {
252+
current = t._1();
253+
}
254+
for (final A a: x.right()) {
255+
return a;
256+
}
257+
}
258+
}
259+
}

0 commit comments

Comments
 (0)