Skip to content

Commit 46c5bcd

Browse files
jnapejnape
committed
Prepromorphism
1 parent 5d42357 commit 46c5bcd

File tree

5 files changed

+106
-4
lines changed

5 files changed

+106
-4
lines changed

‎src/main/java/com/jnape/palatable/lambda/functor/NaturalTransformation.java

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package com.jnape.palatable.lambda.functor;
2+
3+
import com.jnape.palatable.lambda.functions.Fn1;
4+
5+
@FunctionalInterface
6+
public interface NaturalTransformation<A, FA extends Functor<A, ?>, GA extends Functor<A, ?>> extends Fn1<FA, GA> {
7+
8+
static <A, FA extends Functor<A, ?>> NaturalTransformation<A, FA, FA> identity() {
9+
return fa -> fa;
10+
}
11+
}

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,5 +3,6 @@
33
import com.jnape.palatable.lambda.functions.Fn1;
44
import com.jnape.palatable.lambda.functor.Functor;
55

6+
@FunctionalInterface
67
public interface Algebra<F extends Functor<A, ?>, A> extends Fn1<F, A> {
78
}

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

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package com.jnape.palatable.lambda.recursionschemes.builtin;
2+
3+
import com.jnape.palatable.lambda.functions.Fn1;
4+
import com.jnape.palatable.lambda.functions.Fn2;
5+
import com.jnape.palatable.lambda.functions.Fn3;
6+
import com.jnape.palatable.lambda.functor.Functor;
7+
import com.jnape.palatable.lambda.functor.NaturalTransformation;
8+
import com.jnape.palatable.lambda.recursionschemes.Algebra;
9+
import com.jnape.palatable.lambda.recursionschemes.Fix;
10+
11+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Catamorphism.cata;
12+
13+
public final class Prepromorphism<A, F extends Functor, FA extends Functor<A, F>, GA extends Functor<A, F>> implements
14+
Fn3<Algebra<FA, A>, NaturalTransformation<A, GA, FA>, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> {
15+
16+
private static final Prepromorphism INSTANCE = new Prepromorphism();
17+
18+
private Prepromorphism() {
19+
}
20+
21+
@Override
22+
public A apply(Algebra<FA, A> algebra, NaturalTransformation<A, GA, FA> naturalTransformation,
23+
Fix<F, ? extends Functor<? extends Fix<F, ?>, F>> fixed) {
24+
return cata((Algebra<GA, A>) ga -> algebra.apply(naturalTransformation.apply(ga)), fixed);
25+
}
26+
27+
@SuppressWarnings("unchecked")
28+
public static <A, F extends Functor, FA extends Functor<A, F>, GA extends Functor<A, F>> Prepromorphism<A, F, FA, GA> prepro() {
29+
return INSTANCE;
30+
}
31+
32+
public static <A, F extends Functor, FA extends Functor<A, F>, GA extends Functor<A, F>> Fn2<NaturalTransformation<A, GA, FA>, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> prepro(
33+
Algebra<FA, A> algebra) {
34+
return Prepromorphism.<A, F, FA, GA>prepro().apply(algebra);
35+
}
36+
37+
public static <A, F extends Functor, FA extends Functor<A, F>, GA extends Functor<A, F>> Fn1<Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> prepro(
38+
Algebra<FA, A> algebra, NaturalTransformation<A, GA, FA> naturalTransformation) {
39+
return Prepromorphism.<A, F, FA, GA>prepro(algebra).apply(naturalTransformation);
40+
}
41+
42+
public static <A, F extends Functor, FA extends Functor<A, F>, GA extends Functor<A, F>> A prepro(
43+
Algebra<FA, A> algebra,
44+
NaturalTransformation<A, GA, FA> naturalTransformation,
45+
Fix<F, ? extends Functor<? extends Fix<F, ?>, F>> fixed) {
46+
return prepro(algebra, naturalTransformation).apply(fixed);
47+
}
48+
}

‎src/test/java/com/jnape/palatable/lambda/recursionschemes/builtin/PrepromorphismTest.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.jnape.palatable.lambda.recursionschemes.builtin;
2+
3+
import com.jnape.palatable.lambda.functor.NaturalTransformation;
4+
import com.jnape.palatable.lambda.recursionschemes.Algebra;
5+
import org.junit.Test;
6+
import testsupport.recursion.Nat;
7+
import testsupport.recursion.NatF;
8+
9+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Constantly.constantly;
10+
import static com.jnape.palatable.lambda.functions.builtin.fn2.Iterate.iterate;
11+
import static com.jnape.palatable.lambda.functions.builtin.fn2.Map.map;
12+
import static com.jnape.palatable.lambda.functions.builtin.fn2.Take.take;
13+
import static com.jnape.palatable.lambda.recursionschemes.Fix.fix;
14+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Anamorphism.ana;
15+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Catamorphism.cata;
16+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Prepromorphism.prepro;
17+
import static org.junit.Assert.assertEquals;
18+
import static testsupport.recursion.NatF.s;
19+
import static testsupport.recursion.NatF.z;
20+
21+
public class PrepromorphismTest {
22+
23+
@Test
24+
public void foldingThroughFixedPointWithNaturalTransformation() {
25+
Algebra<NatF<Integer>, Integer> sum = natF -> natF.match(z -> 0, s -> 1 + s.carrier());
26+
NaturalTransformation<Integer, NatF<Integer>, NatF<Integer>> times2 = natF -> natF.match(constantly(z()), s -> s(s.carrier() * 2));
27+
28+
assertEquals((Integer) 0, prepro(sum, times2, fix(z())));
29+
assertEquals((Integer) 0, prepro(sum, times2).apply(Nat.z()));
30+
assertEquals((Integer) 1, prepro(sum, times2).apply(fix(NatF.s(fix(z())))));
31+
assertEquals((Integer) 1, prepro(sum, times2).apply(Nat.s(Nat.z())));
32+
assertEquals((Integer) 3, prepro(sum, times2).apply(fix(NatF.s(fix(NatF.s(fix(z())))))));
33+
assertEquals((Integer) 3, prepro(sum, times2).apply(Nat.s(Nat.s(Nat.z()))));
34+
}
35+
36+
@Test
37+
public void prepromorphismWithIdentityNaturalTransformationIsIsomorphicToCatamorphism() {
38+
Algebra<NatF<Integer>, Integer> sum = natF -> natF.match(z -> 0, s -> 1 + s.carrier());
39+
take(100, map(ana(x -> x > 0 ? s(x - 1) : z()), iterate(x -> x + 1, 0)))
40+
.forEach(fix -> assertEquals(cata(sum, fix), prepro(sum, NaturalTransformation.identity(), fix)));
41+
}
42+
}

‎src/test/java/testsupport/recursion/Nat.java

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -4,15 +4,15 @@
44

55
public final class Nat implements Fix<NatF, NatF<Nat>> {
66

7-
private final NatF<Nat> carrier;
7+
private final NatF<Nat> unfixed;
88

9-
private Nat(NatF<Nat> carrier) {
10-
this.carrier = carrier;
9+
private Nat(NatF<Nat> unfixed) {
10+
this.unfixed = unfixed;
1111
}
1212

1313
@Override
1414
public NatF<Nat> unfix() {
15-
return carrier;
15+
return unfixed;
1616
}
1717

1818
public static Nat z() {

0 commit comments

Comments
 (0)