Skip to content

Commit 9038b17

Browse files
jnapejnape
committed
Zygomorphism
1 parent a17aee2 commit 9038b17

File tree

2 files changed

+97
-0
lines changed

2 files changed

+97
-0
lines changed

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

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
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.functions.Fn3;
7+
import com.jnape.palatable.lambda.functor.Functor;
8+
import com.jnape.palatable.lambda.recursionschemes.Algebra;
9+
import com.jnape.palatable.lambda.recursionschemes.Fix;
10+
11+
import java.util.function.Function;
12+
13+
import static com.jnape.palatable.lambda.adt.hlist.HList.tuple;
14+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Catamorphism.cata;
15+
16+
public final class Zygomorphism<A, B, F extends Functor, FB extends Functor<B, F>, FAB extends Functor<Tuple2<A, B>, F>> implements
17+
Fn3<Function<FAB, A>, Algebra<FB, B>, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> {
18+
19+
private static final Zygomorphism INSTANCE = new Zygomorphism();
20+
21+
private Zygomorphism() {
22+
}
23+
24+
@Override
25+
@SuppressWarnings("unchecked")
26+
public A apply(Function<FAB, A> fn, Algebra<FB, B> algebra,
27+
Fix<F, ? extends Functor<? extends Fix<F, ?>, F>> fixed) {
28+
return fn.apply((FAB) fixed.unfix().fmap(f -> {
29+
A a = zygo(fn, algebra, (Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>) f);
30+
B b = cata(algebra, fixed);
31+
return tuple(a, b);
32+
}));
33+
}
34+
35+
@SuppressWarnings("unchecked")
36+
public static <A, B, F extends Functor, FB extends Functor<B, F>, FAB extends Functor<Tuple2<A, B>, F>> Zygomorphism<A, B, F, FB, FAB> zygo() {
37+
return INSTANCE;
38+
}
39+
40+
public static <A, B, F extends Functor, FB extends Functor<B, F>, FAB extends Functor<Tuple2<A, B>, F>> Fn2<Algebra<FB, B>, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> zygo(
41+
Function<FAB, A> fn) {
42+
return Zygomorphism.<A, B, F, FB, FAB>zygo().apply(fn);
43+
}
44+
45+
public static <A, B, F extends Functor, FB extends Functor<B, F>, FAB extends Functor<Tuple2<A, B>, F>> Fn1<Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> zygo(
46+
Function<FAB, A> fn, Algebra<FB, B> algebra) {
47+
return Zygomorphism.<A, B, F, FB, FAB>zygo(fn).apply(algebra);
48+
}
49+
50+
public static <A, B, F extends Functor, FB extends Functor<B, F>, FAB extends Functor<Tuple2<A, B>, F>> A zygo(
51+
Function<FAB, A> fn, Algebra<FB, B> algebra, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>> fixed) {
52+
return zygo(fn, algebra).apply(fixed);
53+
}
54+
}

‎src/test/java/com/jnape/palatable/lambda/recursionschemes/builtin/ZygomorphismTest.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.Algebra;
6+
import org.junit.Test;
7+
import testsupport.recursion.ListF;
8+
import testsupport.recursion.NatF;
9+
10+
import static com.jnape.palatable.lambda.recursionschemes.Fix.fix;
11+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Zygomorphism.zygo;
12+
import static org.junit.Assert.assertEquals;
13+
import static testsupport.recursion.List.cons;
14+
import static testsupport.recursion.List.nil;
15+
import static testsupport.recursion.Nat.s;
16+
import static testsupport.recursion.Nat.z;
17+
18+
public class ZygomorphismTest {
19+
20+
@Test
21+
public void foldsThroughLeastFixedPointWithParallelAlgebra() {
22+
Algebra<NatF<Integer>, Integer> sumNat = natF -> natF.match(z -> 0, s -> s.carrier() + 1);
23+
Fn1<NatF<Tuple2<String, Integer>>, String> natFString =
24+
natF -> natF.match(z -> "_", s -> s.carrier().into((x, y) -> x + " : {" + y + "}"));
25+
26+
assertEquals("_", zygo(natFString, sumNat, fix(NatF.z())));
27+
assertEquals("_", zygo(natFString, sumNat, z()));
28+
29+
assertEquals("_ : {1} : {2} : {3}", zygo(natFString, sumNat, fix(NatF.s(fix(NatF.s(fix(NatF.s(fix(NatF.z())))))))));
30+
assertEquals("_ : {1} : {2} : {3}", zygo(natFString, sumNat, s(s(s(z())))));
31+
32+
Algebra<ListF<Integer, Integer>, Integer> sumList = listF -> listF.match(nil -> 0, cons -> cons.head() + cons.tail());
33+
Fn1<ListF<Integer, Tuple2<String, Integer>>, String> listFString =
34+
listF -> listF.match(nil -> "_",
35+
cons -> "{" + cons.head() + " : " + cons.tail().into((x, y) -> "(" + x + ", " + y + ")") + "}");
36+
37+
assertEquals("_", zygo(listFString, sumList, fix(ListF.nil())));
38+
assertEquals("_", zygo(listFString, sumList, nil()));
39+
40+
assertEquals("{3 : ({2 : ({1 : (_, 1)}, 3)}, 6)}", zygo(listFString, sumList, fix(ListF.cons(3, fix(ListF.cons(2, fix(ListF.cons(1, fix(ListF.nil())))))))));
41+
assertEquals("{3 : ({2 : ({1 : (_, 1)}, 3)}, 6)}", zygo(listFString, sumList, cons(3, cons(2, cons(1, nil())))));
42+
}
43+
}

0 commit comments

Comments
 (0)