Skip to content

Commit b92670c

Browse files
jnapejnape
committed
Adding Free
1 parent d95e2e5 commit b92670c

File tree

3 files changed

+143
-19
lines changed

3 files changed

+143
-19
lines changed

‎src/main/java/com/jnape/palatable/lambda/recursionschemes/Free.java

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
package com.jnape.palatable.lambda.recursionschemes;
2+
3+
import com.jnape.palatable.lambda.adt.choice.Choice2;
4+
import com.jnape.palatable.lambda.adt.coproduct.CoProduct2;
5+
import com.jnape.palatable.lambda.functor.Functor;
6+
import fix.Coalgebra;
7+
8+
import java.util.function.Function;
9+
10+
import static com.jnape.palatable.lambda.adt.choice.Choice2.a;
11+
import static com.jnape.palatable.lambda.adt.choice.Choice2.b;
12+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Anamorphism.ana;
13+
14+
/**
15+
* The free monad. <code>Free</code> can be thought of as adding the capabilities of a pattern functor to a functor
16+
* that has no zero construction -- that is, a functor that has no constructions for which <code>f.fmap(fn) ==
17+
* f</code>.
18+
* <p>
19+
* Consider the example where some functor <code>f</code> has no zero construction; fixing <code>f</code> is rendered
20+
* impossible by construction, since there can be no terminating expression. Conversely, {@link Free#pure} provides an
21+
* escape-hatch to terminate the expression recursion, allowing construction of fix-like expressions for functors that
22+
* otherwise would not support this.
23+
*
24+
* @param <A> the type of the expression-terminating pure value
25+
* @param <F> the functor unification type
26+
* @param <FreeF> the type corresponding to the functor that wraps Free
27+
*/
28+
public final class Free<A, F extends Functor, FreeF extends Functor<?, F>> implements CoProduct2<A, FreeF> {
29+
private final Choice2<A, FreeF> choice;
30+
31+
private Free(Choice2<A, FreeF> choice) {
32+
this.choice = choice;
33+
}
34+
35+
/**
36+
* Given a {@link Coalgebra}, recursively fold this <code>Free</code> into a {@link Fix}. Note that this is only
37+
* achievable for pattern functors, as the pure anamorphism will only terminate once a zero construction is reached.
38+
*
39+
* @param coalgebra the coalgebra to use to convert a pure value into a Fix
40+
* @param <FA> the functor type the coalgebra unwraps the value from
41+
* @return the fix version of this free
42+
*/
43+
@SuppressWarnings("unchecked")
44+
public <FA extends Functor<A, F>> Fix<F, ? extends Functor<? extends Fix<F, ?>, F>> fix(
45+
Coalgebra<A, FA> coalgebra) {
46+
return match(a -> ana(coalgebra, a),
47+
freeF -> Fix.fix(freeF.fmap(x1 -> ((Free<A, F, FreeF>) x1).fix(coalgebra))));
48+
}
49+
50+
@Override
51+
public <R> R match(Function<? super A, ? extends R> aFn, Function<? super FreeF, ? extends R> bFn) {
52+
return choice.match(aFn, bFn);
53+
}
54+
55+
@Override
56+
public boolean equals(Object other) {
57+
return other instanceof Free && choice.equals(((Free) other).choice);
58+
}
59+
60+
@Override
61+
public int hashCode() {
62+
return choice.hashCode();
63+
}
64+
65+
/**
66+
* The recursive expression in free construction, using a functor.
67+
*
68+
* @param f the functor
69+
* @param <A> the pure parameter type
70+
* @param <F> the functor unification type
71+
* @param <FreeF> the type corresponding to the functor that wraps Free
72+
* @return an instance of Free over this functor
73+
*/
74+
public static <A, F extends Functor, FreeF extends Functor<? extends Free<A, F, ?>, F>> Free<A, F, FreeF> free(
75+
FreeF f) {
76+
return new Free<>(b(f));
77+
}
78+
79+
/**
80+
* The terminating expression in free construction, using a value.
81+
*
82+
* @param a the pure value
83+
* @param <A> the pure parameter type
84+
* @param <F> the functor unification type
85+
* @param <FreeF> the type corresponding to the functor that wraps Free
86+
* @return an instance of Free over this value
87+
*/
88+
public static <A, F extends Functor, FreeF extends Functor<?, F>> Free<A, F, FreeF> pure(A a) {
89+
return new Free<>(a(a));
90+
}
91+
}

‎src/main/java/com/jnape/palatable/lambda/recursionschemes/builtin/Hylomorphism.java

Lines changed: 2 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,6 @@
55
import com.jnape.palatable.lambda.functions.Fn3;
66
import com.jnape.palatable.lambda.functor.Functor;
77
import com.jnape.palatable.lambda.recursionschemes.Algebra;
8-
import com.jnape.palatable.lambda.recursionschemes.Thunk;
98
import fix.Coalgebra;
109

1110
import static com.jnape.palatable.lambda.recursionschemes.builtin.Anamorphism.ana;
@@ -19,7 +18,7 @@ private Hylomorphism() {
1918
}
2019

2120
@SuppressWarnings({"unchecked", "Duplicates"})
22-
public A fapply(Algebra<FA, A> algebra, Coalgebra<A, FA> coalgebra, A a) {
21+
public A effortTowardsFusion(Algebra<FA, A> algebra, Coalgebra<A, FA> coalgebra, A a) {
2322
A x = a;
2423
FA fa = coalgebra.apply(x);
2524
FA previous = null;
@@ -34,24 +33,8 @@ public A fapply(Algebra<FA, A> algebra, Coalgebra<A, FA> coalgebra, A a) {
3433
return x;
3534
}
3635

37-
@SuppressWarnings({"unchecked", "Duplicates"})
38-
public B fapply2(Algebra<FB, B> algebra, Coalgebra<A, FA> coalgebra, A a) {
39-
A x = a;
40-
B currentB = null;
41-
FA fa = coalgebra.apply(x);
42-
FA previous = null;
43-
while (fa != previous) {
44-
previous = fa;
45-
final FA foo = fa;
46-
Thunk<B, F> bfThunk = new Thunk<>(() -> foo.fmap(a1 -> fapply2(algebra, coalgebra, a1)));
47-
currentB = algebra.apply((FB) bfThunk.get());
48-
}
49-
return currentB;
50-
}
51-
52-
5336
@Override
54-
@SuppressWarnings({"unchecked", "Duplicates"})
37+
@SuppressWarnings("unchecked")
5538
public B apply(Algebra<FB, B> algebra, Coalgebra<A, FA> coalgebra, A a) {
5639
return cata(algebra).compose(ana(coalgebra)).apply(a);
5740
}

‎src/test/java/com/jnape/palatable/lambda/recursionschemes/FreeTest.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package com.jnape.palatable.lambda.recursionschemes;
2+
3+
import fix.Coalgebra;
4+
import org.junit.Test;
5+
import testsupport.recursion.ListF;
6+
import testsupport.recursion.NatF;
7+
8+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Id.id;
9+
import static com.jnape.palatable.lambda.recursionschemes.Fix.fix;
10+
import static com.jnape.palatable.lambda.recursionschemes.Free.free;
11+
import static com.jnape.palatable.lambda.recursionschemes.Free.pure;
12+
import static org.junit.Assert.assertEquals;
13+
import static testsupport.recursion.ListF.cons;
14+
import static testsupport.recursion.ListF.nil;
15+
import static testsupport.recursion.NatF.s;
16+
import static testsupport.recursion.NatF.z;
17+
18+
public class FreeTest {
19+
20+
@Test
21+
@SuppressWarnings("unused")
22+
public void validTypeSafeSignatures() {
23+
Free<Integer, NatF, NatF<Free<Integer, NatF, NatF<Free<Integer, NatF, NatF<Free<Integer, NatF, ?>>>>>>> losslessNatFWithPure = free(s(free(s(pure(0)))));
24+
Free<Integer, NatF, NatF<Free<Integer, NatF, NatF<Free<Integer, NatF, NatF<Free<Integer, NatF, ?>>>>>>> losslessNatFWithoutPure = free(s(free(s(free(z())))));
25+
Free<Integer, NatF, NatF<Free<Integer, NatF, ?>>> compactNatFWithPure = free(s(free(s(pure(0)))));
26+
Free<Integer, NatF, NatF<Free<Integer, NatF, ?>>> compactNatFWithoutPure = free(s(free(s(free(z())))));
27+
Free<Integer, NatF, ?> minimalNatFWithPure = free(s(free(s(pure(0)))));
28+
Free<Integer, NatF, ?> minimalNatFWithoutPure = free(s(free(s(free(z())))));
29+
30+
Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ?>>>>>>>>> losslessListFWithPure = free(cons(3, free(cons(2, free(cons(1, pure(0)))))));
31+
Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ?>>>>>>>>> losslessListFWithoutPure = free(cons(3, free(cons(2, free(cons(1, free(nil())))))));
32+
Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ?>>> compactListFWithPure = free(cons(3, free(cons(2, free(cons(1, pure(0)))))));
33+
Free<Integer, ListF<Integer, ?>, ListF<Integer, Free<Integer, ListF<Integer, ?>, ?>>> compactListFWithoutPure = free(cons(3, free(cons(2, free(cons(1, free(nil())))))));
34+
Free<Integer, ListF<Integer, ?>, ?> minimalListFWithPure = free(cons(3, free(cons(2, free(cons(1, pure(0)))))));
35+
Free<Integer, ListF<Integer, ?>, ?> minimalListFWithoutPure = free(cons(3, free(cons(2, free(cons(1, free(nil())))))));
36+
}
37+
38+
@Test
39+
public void coproduct() {
40+
assertEquals(z(), free(z()).match(id(), id()));
41+
assertEquals(0, pure(0).match(id(), id()));
42+
}
43+
44+
@Test
45+
public void foldsIntoFix() {
46+
Coalgebra<Integer, NatF<Integer>> nats = x -> x == 0 ? z() : s(x - 1);
47+
assertEquals(free(s(free(s(free(s(pure(0))))))).fix(nats), fix(s(fix(s(fix(s(fix(z()))))))));
48+
assertEquals(free(s(free(s(free(s(pure(1))))))).fix(nats), fix(s(fix(s(fix(s(fix(s(fix(z()))))))))));
49+
}
50+
}

0 commit comments

Comments
 (0)