Skip to content

Commit a17aee2

Browse files
jnapejnape
committed
Adding paramorphism
1 parent 68b90a3 commit a17aee2

File tree

7 files changed

+129
-1
lines changed

7 files changed

+129
-1
lines changed

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,11 @@ public boolean equals(Object obj) {
5353
public int hashCode() {
5454
return 31 * Objects.hashCode(unfixed);
5555
}
56+
57+
@Override
58+
public String toString() {
59+
return "fix(" + unfixed + ")";
60+
}
5661
};
5762
}
5863
}

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,8 @@
66
import com.jnape.palatable.lambda.recursionschemes.Algebra;
77
import com.jnape.palatable.lambda.recursionschemes.Fix;
88

9-
public final class Catamorphism<A, F extends Functor, FA extends Functor<A, F>> implements Fn2<Algebra<FA, A>, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> {
9+
public final class Catamorphism<A, F extends Functor, FA extends Functor<A, F>> implements
10+
Fn2<Algebra<FA, A>, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> {
1011

1112
private static final Catamorphism INSTANCE = new Catamorphism();
1213

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

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.jnape.palatable.lambda.recursionschemes.builtin;
2+
3+
import com.jnape.palatable.lambda.adt.hlist.Tuple2;
4+
import com.jnape.palatable.lambda.functions.Fn1;
5+
import com.jnape.palatable.lambda.functions.Fn2;
6+
import com.jnape.palatable.lambda.functor.Functor;
7+
import com.jnape.palatable.lambda.recursionschemes.Algebra;
8+
import com.jnape.palatable.lambda.recursionschemes.Fix;
9+
10+
import java.util.function.Function;
11+
12+
import static com.jnape.palatable.lambda.adt.hlist.HList.tuple;
13+
import static com.jnape.palatable.lambda.recursionschemes.Fix.fix;
14+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Catamorphism.cata;
15+
16+
public final class Paramorphism<A, F extends Functor, Tuple extends Tuple2<? extends Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A>, FA extends Functor<Tuple, F>>
17+
implements Fn2<Function<FA, A>, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> {
18+
private static final Paramorphism INSTANCE = new Paramorphism();
19+
20+
private Paramorphism() {
21+
}
22+
23+
@Override
24+
@SuppressWarnings("unchecked")
25+
public A apply(Function<FA, A> fn, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>> fixed) {
26+
Algebra<FA, Tuple> algebra = fa -> (Tuple) tuple(fix(fa.fmap(Tuple2::_1)), fn.apply(fa));
27+
return cata(algebra, fixed)._2();
28+
}
29+
30+
@SuppressWarnings("unchecked")
31+
public static <A, F extends Functor, Tuple extends Tuple2<? extends Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A>, FA extends Functor<Tuple, F>> Paramorphism<A, F, Tuple, FA> para() {
32+
return (Paramorphism<A, F, Tuple, FA>) INSTANCE;
33+
}
34+
35+
public static <A, F extends Functor, Tuple extends Tuple2<? extends Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A>, FA extends Functor<Tuple, F>> Fn1<Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> para(
36+
Function<FA, A> fn) {
37+
return Paramorphism.<A, F, Tuple, FA>para().apply(fn);
38+
}
39+
40+
public static <A, F extends Functor, Tuple extends Tuple2<? extends Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A>, FA extends Functor<Tuple, F>> A para(
41+
Function<FA, A> fn, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>> fixed) {
42+
return para(fn).apply(fixed);
43+
}
44+
}

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

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package com.jnape.palatable.lambda.recursionschemes.builtin;
2+
3+
import com.jnape.palatable.lambda.adt.hlist.Tuple2;
4+
import com.jnape.palatable.lambda.functions.Fn1;
5+
import com.jnape.palatable.lambda.recursionschemes.Fix;
6+
import org.junit.Test;
7+
import testsupport.recursion.List;
8+
import testsupport.recursion.ListF;
9+
import testsupport.recursion.NatF;
10+
11+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Constantly.constantly;
12+
import static com.jnape.palatable.lambda.recursionschemes.Fix.fix;
13+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Paramorphism.para;
14+
import static org.junit.Assert.assertEquals;
15+
import static testsupport.recursion.List.cons;
16+
import static testsupport.recursion.List.nil;
17+
import static testsupport.recursion.Nat.s;
18+
import static testsupport.recursion.Nat.z;
19+
20+
public class ParamorphismTest {
21+
22+
@Test
23+
public void foldingThroughLeastFixedPointRetainingSubtree() {
24+
Fn1<NatF<Tuple2<Fix<NatF, NatF<Fix<NatF, ?>>>, Integer>>, Integer> sum =
25+
nat -> nat.match(constantly(0), s -> s.carrier()._2() + 1);
26+
27+
assertEquals((Integer) 0, para(sum, fix(NatF.z())));
28+
assertEquals((Integer) 0, para(sum, z()));
29+
30+
assertEquals((Integer) 3, para(sum, fix(NatF.s(fix(NatF.s(fix(NatF.s(fix(NatF.z())))))))));
31+
assertEquals((Integer) 3, para(sum, s(s(s(z())))));
32+
33+
Fn1<ListF<Integer, Tuple2<Fix<ListF<Integer, ?>, ListF<Integer, Fix<ListF<Integer, ?>, ?>>>, List<String>>>, List<String>> stringify =
34+
listF -> listF.match(nil -> nil(),
35+
cons -> cons(cons.head().toString(), cons.tail()._2()));
36+
37+
assertEquals(nil(), para(stringify, fix(ListF.nil())));
38+
assertEquals(nil(), para(stringify, nil()));
39+
40+
assertEquals(cons("3", cons("2", cons("1", nil()))), para(stringify, fix(ListF.cons(3, fix(ListF.cons(2, fix(ListF.cons(1, fix(ListF.nil())))))))));
41+
assertEquals(cons("3", cons("2", cons("1", nil()))), para(stringify, cons(3, cons(2, cons(1, nil())))));
42+
}
43+
}

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

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,21 @@ public ListF<A, List<A>> unfix() {
1515
return unfixed;
1616
}
1717

18+
@Override
19+
public boolean equals(Object other) {
20+
return other instanceof List && unfixed.equals(((List) other).unfix());
21+
}
22+
23+
@Override
24+
public int hashCode() {
25+
return unfixed.hashCode();
26+
}
27+
28+
@Override
29+
public String toString() {
30+
return unfixed.toString();
31+
}
32+
1833
public static <A> List<A> nil() {
1934
return new List<>(ListF.nil());
2035
}

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

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -39,6 +39,11 @@ public boolean equals(Object obj) {
3939
public int hashCode() {
4040
return 31;
4141
}
42+
43+
@Override
44+
public String toString() {
45+
return "nil()";
46+
}
4247
}
4348

4449
public static final class Cons<A, B> extends ListF<A, B> {
@@ -84,5 +89,10 @@ public boolean equals(Object obj) {
8489
public int hashCode() {
8590
return 31 * Objects.hashCode(head) + Objects.hashCode(tail);
8691
}
92+
93+
@Override
94+
public String toString() {
95+
return "cons(" + head + ", " + tail + ")";
96+
}
8797
}
8898
}

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

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,11 @@ public boolean equals(Object obj) {
4141
public int hashCode() {
4242
return 31;
4343
}
44+
45+
@Override
46+
public String toString() {
47+
return "z()";
48+
}
4449
}
4550

4651
public static final class S<A> extends NatF<A> {
@@ -69,5 +74,10 @@ public <R> R match(Function<? super Z<A>, ? extends R> aFn, Function<? super S<A
6974
public boolean equals(Object obj) {
7075
return obj instanceof S && Objects.equals(carrier(), ((S) obj).carrier());
7176
}
77+
78+
@Override
79+
public String toString() {
80+
return "s(" + a + ")";
81+
}
7282
}
7383
}

0 commit comments

Comments
 (0)