Skip to content

Commit 41418b0

Browse files
jnapejnape
committed
Histomorphism
1 parent 9038b17 commit 41418b0

File tree

7 files changed

+143
-19
lines changed

7 files changed

+143
-19
lines changed

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

Lines changed: 39 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2,15 +2,49 @@
22

33
import com.jnape.palatable.lambda.adt.hlist.Tuple2;
44
import com.jnape.palatable.lambda.functor.Functor;
5+
import com.jnape.palatable.lambda.recursionschemes.builtin.Histomorphism;
56

67
import static com.jnape.palatable.lambda.adt.hlist.HList.tuple;
78

8-
public interface Cofree<A, F extends Functor, CofreeF extends Functor<?, F>> {
9+
/**
10+
* The combination of the least fixed point of a given functor and a value annotation. Useful for adding additional
11+
* information to individual levels of nesting for memoization.
12+
*
13+
* @param <F> the functor unification type
14+
* @param <A> the annotation value type
15+
* @param <CofreeF> the type corresponding to the unfixed functor
16+
* @see Histomorphism
17+
*/
18+
public interface Cofree<F extends Functor, A, CofreeF extends Functor<?, F>> {
919

10-
Tuple2<A, CofreeF> uncofree();
20+
/**
21+
* Produce the internal structure represented by this cofree.
22+
*
23+
* @return a tuple of the functor and the value
24+
*/
25+
Tuple2<CofreeF, A> uncofree();
1126

12-
static <A, F extends Functor, CofreeF extends Functor<? extends Cofree<A, F, ?>, F>> Cofree<A, F, CofreeF> coFree(
13-
A a, CofreeF f) {
14-
return () -> tuple(a, f);
27+
/**
28+
* Convenience method for extracting the annotation value from teh internal structure of this cofree.
29+
*
30+
* @return the annotation value
31+
*/
32+
default A attr() {
33+
return uncofree()._2();
34+
}
35+
36+
/**
37+
* Fix and attach an annotation value to a {@link Functor}.
38+
*
39+
* @param f the unfixed functor
40+
* @param a the annotation value
41+
* @param <A> the annotation value type
42+
* @param <F> the functor unification tyep
43+
* @param <CofreeF> the type corresponding to the unfixed functor
44+
* @return a cofree joining the fixed functor to the annotation value
45+
*/
46+
static <A, F extends Functor, CofreeF extends Functor<? extends Cofree<F, A, ?>, F>> Cofree<F, A, CofreeF> cofree(
47+
CofreeF f, A a) {
48+
return () -> tuple(f, a);
1549
}
1650
}

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

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,12 @@
11
package com.jnape.palatable.lambda.recursionschemes;
22

33
import com.jnape.palatable.lambda.functor.Functor;
4+
import com.jnape.palatable.lambda.recursionschemes.builtin.Anamorphism;
5+
import com.jnape.palatable.lambda.recursionschemes.builtin.Catamorphism;
6+
import com.jnape.palatable.lambda.recursionschemes.builtin.Histomorphism;
7+
import com.jnape.palatable.lambda.recursionschemes.builtin.Hylomorphism;
8+
import com.jnape.palatable.lambda.recursionschemes.builtin.Paramorphism;
9+
import com.jnape.palatable.lambda.recursionschemes.builtin.Zygomorphism;
410

511
import java.util.Objects;
612

@@ -18,6 +24,12 @@
1824
*
1925
* @param <F> the functor unification type
2026
* @param <Unfixed> the type corresponding to the unfixed functor
27+
* @see Anamorphism
28+
* @see Catamorphism
29+
* @see Histomorphism
30+
* @see Hylomorphism
31+
* @see Paramorphism
32+
* @see Zygomorphism
2133
*/
2234
@FunctionalInterface
2335
public interface Fix<F extends Functor, Unfixed extends Functor<?, ? extends F>> {

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

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,6 @@
55
import com.jnape.palatable.lambda.functor.Functor;
66
import com.jnape.palatable.lambda.recursionschemes.Coalgebra;
77
import com.jnape.palatable.lambda.recursionschemes.Fix;
8-
import com.jnape.palatable.lambda.recursionschemes.Thunk;
98

109
import static com.jnape.palatable.lambda.recursionschemes.Fix.fix;
1110

@@ -18,7 +17,7 @@ private Anamorphism() {
1817

1918
@Override
2019
public Fix<F, Functor<Fix<F, ?>, F>> apply(Coalgebra<A, FA> coalgebra, A a) {
21-
return fix(new Thunk<>(() -> coalgebra.apply(a)).<Fix<F, ?>>fmap(ana(coalgebra)).get());
20+
return fix(coalgebra.apply(a).fmap(ana(coalgebra)));
2221
}
2322

2423
@SuppressWarnings("unchecked")

‎src/main/java/com/jnape/palatable/lambda/recursionschemes/builtin/Histomorphism.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.functions.Fn1;
4+
import com.jnape.palatable.lambda.functions.Fn2;
5+
import com.jnape.palatable.lambda.functor.Functor;
6+
import com.jnape.palatable.lambda.recursionschemes.Algebra;
7+
import com.jnape.palatable.lambda.recursionschemes.Cofree;
8+
import com.jnape.palatable.lambda.recursionschemes.Fix;
9+
10+
import java.util.function.Function;
11+
12+
import static com.jnape.palatable.lambda.recursionschemes.Cofree.cofree;
13+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Catamorphism.cata;
14+
15+
public final class Histomorphism<A, F extends Functor, CofreeF extends Functor<Cofree<F, A, ?>, F>>
16+
implements Fn2<Function<CofreeF, A>, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> {
17+
18+
private static final Histomorphism INSTANCE = new Histomorphism();
19+
20+
private Histomorphism() {
21+
}
22+
23+
@Override
24+
public A apply(Function<CofreeF, A> fn, Fix<F, ? extends Functor<? extends Fix<F, ?>, F>> fix) {
25+
return cata((Algebra<CofreeF, Cofree<F, A, ?>>) cofreeF -> cofree(cofreeF, fn.apply(cofreeF)), fix)
26+
.attr();
27+
}
28+
29+
@SuppressWarnings("unchecked")
30+
public static <A, F extends Functor, CofreeF extends Functor<Cofree<F, A, ?>, F>> Histomorphism<A, F, CofreeF> histo() {
31+
return INSTANCE;
32+
}
33+
34+
public static <A, F extends Functor, CofreeF extends Functor<Cofree<F, A, ?>, F>> Fn1<Fix<F, ? extends Functor<? extends Fix<F, ?>, F>>, A> histo(
35+
Function<CofreeF, A> fn) {
36+
return Histomorphism.<A, F, CofreeF>histo().apply(fn);
37+
}
38+
39+
public static <A, F extends Functor, CofreeF extends Functor<Cofree<F, A, ?>, F>> A histo(
40+
Function<CofreeF, A> fn,
41+
Fix<F, ? extends Functor<? extends Fix<F, ?>, F>> fix) {
42+
return histo(fn).apply(fix);
43+
}
44+
}

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

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.jnape.palatable.lambda.recursionschemes;
2+
3+
import org.junit.Test;
4+
import testsupport.recursion.ListF;
5+
import testsupport.recursion.NatF;
6+
7+
import static com.jnape.palatable.lambda.recursionschemes.Cofree.cofree;
8+
import static testsupport.recursion.ListF.cons;
9+
import static testsupport.recursion.ListF.nil;
10+
import static testsupport.recursion.NatF.s;
11+
import static testsupport.recursion.NatF.z;
12+
13+
public class CofreeTest {
14+
15+
@Test
16+
@SuppressWarnings("unused")
17+
public void validTypeSafeSignatures() {
18+
Cofree<NatF, Integer, NatF<Cofree<NatF, Integer, NatF<Cofree<NatF, Integer, NatF<Cofree<NatF, Integer, ?>>>>>>> losslessNatF = cofree(s(cofree(s(cofree(z(), 1)), 2)), 3);
19+
Cofree<NatF, Integer, NatF<Cofree<NatF, Integer, ?>>> compactNatF = cofree(s(cofree(s(cofree(z(), 1)), 2)), 3);
20+
Cofree<NatF, ?, ?> minimalNatF = cofree(s(cofree(s(cofree(z(), 1)), 2)), 3);
21+
22+
Cofree<ListF<Integer, ?>, Integer, ListF<Integer, Cofree<ListF<Integer, ?>, Integer, ListF<Integer, Cofree<ListF<Integer, ?>, Integer, ListF<Integer, Cofree<ListF<Integer, ?>, Integer, ?>>>>>>> losslessListF = cofree(cons(2, cofree(cons(1, cofree(nil(), 0)), -1)), -2);
23+
Cofree<ListF<Integer, ?>, Integer, ListF<Integer, Cofree<ListF<Integer, ?>, Integer, ?>>> compactListF = cofree(cons(2, cofree(cons(1, cofree(nil(), 0)), -1)), -2);
24+
Cofree<ListF<Integer, ?>, ?, ?> minimalListF = cofree(cons(2, cofree(cons(1, cofree(nil(), 0)), -1)), -2);
25+
}
26+
}

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

Lines changed: 1 addition & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,7 @@
11
package com.jnape.palatable.lambda.recursionschemes.builtin;
22

3-
import com.jnape.palatable.lambda.recursionschemes.Algebra;
4-
import com.jnape.palatable.lambda.recursionschemes.Fix;
53
import com.jnape.palatable.lambda.recursionschemes.Coalgebra;
4+
import com.jnape.palatable.lambda.recursionschemes.Fix;
65
import org.junit.Test;
76
import testsupport.recursion.ListF;
87
import testsupport.recursion.NatF;
@@ -24,14 +23,4 @@ public void unfoldingToGreatestFixedPoint() {
2423
assertEquals(Fix.<ListF<Integer, ?>, ListF<Integer, Fix<ListF<Integer, ?>, ?>>>fix(ListF.cons(0, fix(ListF.cons(1, fix(ListF.cons(2, fix(ListF.nil()))))))),
2524
ana(elements, 0));
2625
}
27-
28-
// @Test
29-
//todo: wip
30-
public void unfoldingInfiniteCodata() {
31-
Coalgebra<Integer, NatF<Integer>> naturals = i -> NatF.s(i + 1);
32-
Algebra<NatF<String>, String> sum = nat -> nat.match(z -> "0", s -> s.carrier() + 1);
33-
String x = Hylomorphism.<Integer, String, NatF, NatF<Integer>, NatF<String>>hylo().apply(sum, naturals, 0);
34-
System.out.println(x);
35-
36-
}
3726
}

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

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package com.jnape.palatable.lambda.recursionschemes.builtin;
2+
3+
import com.jnape.palatable.lambda.recursionschemes.Cofree;
4+
import com.jnape.palatable.lambda.recursionschemes.Fix;
5+
import org.junit.Test;
6+
import testsupport.recursion.NatF;
7+
8+
import java.util.function.Function;
9+
10+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Histomorphism.histo;
11+
12+
public class HistomorphismTest {
13+
14+
@Test
15+
public void foldingThroughLeastFixedPointRetainingFullTree() {
16+
Integer foo = histo((Function<NatF<Cofree<NatF, Integer, ?>>, Integer>) natF -> natF.match(z -> 0, s -> 1 + s.carrier().attr()),
17+
Fix.fix(NatF.s(Fix.fix(NatF.z()))));
18+
System.out.println(foo);
19+
}
20+
}

0 commit comments

Comments
 (0)