Skip to content

Commit ee6efc8

Browse files
jnapejnape
committed
Initial attempt at approximation of anamorphism
1 parent 131cd95 commit ee6efc8

6 files changed

Lines changed: 127 additions & 1 deletion

File tree

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

Lines changed: 18 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22

33
import com.jnape.palatable.lambda.functor.Functor;
44

5+
import java.util.Objects;
6+
57
/**
68
* A type-level encoding of the least fixed point of a given functor; that is, given a <code>{@link
79
* Functor}&lt;X&gt;</code> <code>f</code> and a value <code>x</code> of type <code>X</code>, <code>x</code> is the
@@ -36,7 +38,22 @@ public interface Fix<F extends Functor, Unfixed extends Functor<?, ? extends F>>
3638
* @return the fixed functor
3739
*/
3840
static <F extends Functor, Unfixed extends Functor<? extends Fix<F, ?>, F>> Fix<F, Unfixed> fix(Unfixed unfixed) {
39-
return () -> unfixed;
41+
return new Fix<F, Unfixed>() {
42+
@Override
43+
public Unfixed unfix() {
44+
return unfixed;
45+
}
46+
47+
@Override
48+
public boolean equals(Object obj) {
49+
return (obj instanceof Fix) && Objects.equals(unfixed, ((Fix) obj).unfix());
50+
}
51+
52+
@Override
53+
public int hashCode() {
54+
return 31 * Objects.hashCode(unfixed);
55+
}
56+
};
4057
}
4158
}
4259

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

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
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.Fix;
7+
import fix.Coalgebra;
8+
9+
import static com.jnape.palatable.lambda.recursionschemes.Fix.fix;
10+
11+
public class Anamorphism<A, F extends Functor, FA extends Functor<A, F>> implements Fn2<Coalgebra<A, FA>, A, Fix<F, Functor<Fix<F, ?>, F>>> {
12+
13+
private static final Anamorphism INSTANCE = new Anamorphism();
14+
15+
@Override
16+
public Fix<F, Functor<Fix<F, ?>, F>> apply(Coalgebra<A, FA> coalgebra, A a) {
17+
return fix(coalgebra.apply(a).fmap(x -> ana(coalgebra, x)));
18+
}
19+
20+
@SuppressWarnings("unchecked")
21+
public static <A, F extends Functor, FA extends Functor<A, F>> Anamorphism<A, F, FA> ana() {
22+
return INSTANCE;
23+
}
24+
25+
public static <A, F extends Functor, FA extends Functor<A, F>> Fn1<A, Fix<F, Functor<Fix<F, ?>, F>>> ana(
26+
Coalgebra<A, FA> coalgebra) {
27+
return Anamorphism.<A, F, FA>ana().apply(coalgebra);
28+
}
29+
30+
public static <A, F extends Functor, FA extends Functor<A, F>> Fix<F, Functor<Fix<F, ?>, F>> ana(
31+
Coalgebra<A, FA> coalgebra, A a) {
32+
return ana(coalgebra).apply(a);
33+
}
34+
}

‎src/main/java/fix/Coalgebra.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package fix;
2+
3+
import com.jnape.palatable.lambda.functions.Fn1;
4+
import com.jnape.palatable.lambda.functor.Functor;
5+
6+
@FunctionalInterface
7+
public interface Coalgebra<A, F extends Functor<A, ?>> extends Fn1<A, F> {
8+
}

‎src/test/java/com/jnape/palatable/lambda/recursionschemes/builtin/AnamorphismTest.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.builtin;
2+
3+
import com.jnape.palatable.lambda.recursionschemes.Fix;
4+
import fix.Coalgebra;
5+
import org.junit.Test;
6+
import testsupport.recursion.ListF;
7+
import testsupport.recursion.NatF;
8+
9+
import static com.jnape.palatable.lambda.recursionschemes.Fix.fix;
10+
import static com.jnape.palatable.lambda.recursionschemes.builtin.Anamorphism.ana;
11+
import static org.junit.Assert.assertEquals;
12+
13+
public class AnamorphismTest {
14+
15+
@Test
16+
public void unfoldingToGreatestFixedPoint() {
17+
Coalgebra<Integer, NatF<Integer>> naturals = x -> x >= 3 ? NatF.z() : NatF.s(x + 1);
18+
assertEquals(Fix.fix(NatF.z()), ana(naturals, 3));
19+
assertEquals(Fix.<NatF, NatF<Fix<NatF, ?>>>fix(NatF.s(fix(NatF.s(fix(NatF.s(fix(NatF.z()))))))), ana(naturals, 0));
20+
21+
Coalgebra<Integer, ListF<Integer, Integer>> elements = x -> x >= 3 ? ListF.nil() : ListF.cons(x, x + 1);
22+
assertEquals(Fix.fix(ListF.nil()), ana(elements, 4));
23+
assertEquals(Fix.<ListF<Integer, ?>, ListF<Integer, Fix<ListF<Integer, ?>, ?>>>fix(ListF.cons(0, fix(ListF.cons(1, fix(ListF.cons(2, fix(ListF.nil()))))))),
24+
ana(elements, 0));
25+
}
26+
}

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

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
import com.jnape.palatable.lambda.adt.coproduct.CoProduct2;
44
import com.jnape.palatable.lambda.functor.Functor;
55

6+
import java.util.Objects;
67
import java.util.function.Function;
78

89
public abstract class ListF<A, B> implements Functor<B, ListF<A, ?>>, CoProduct2<ListF.Nil<A, B>, ListF.Cons<A, B>> {
@@ -28,6 +29,16 @@ public <R> R match(Function<? super Nil<A, B>, ? extends R> aFn,
2829
Function<? super Cons<A, B>, ? extends R> bFn) {
2930
return aFn.apply(this);
3031
}
32+
33+
@Override
34+
public boolean equals(Object obj) {
35+
return obj instanceof Nil;
36+
}
37+
38+
@Override
39+
public int hashCode() {
40+
return 31;
41+
}
3142
}
3243

3344
public static final class Cons<A, B> extends ListF<A, B> {
@@ -59,5 +70,19 @@ public <R> R match(Function<? super Nil<A, B>, ? extends R> aFn,
5970
Function<? super Cons<A, B>, ? extends R> bFn) {
6071
return bFn.apply(this);
6172
}
73+
74+
@Override
75+
public boolean equals(Object obj) {
76+
if (obj instanceof Cons) {
77+
Cons that = (Cons) obj;
78+
return Objects.equals(head, that.head) && Objects.equals(tail, that.tail);
79+
}
80+
return false;
81+
}
82+
83+
@Override
84+
public int hashCode() {
85+
return 31 * Objects.hashCode(head) + Objects.hashCode(tail);
86+
}
6287
}
6388
}

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

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
import com.jnape.palatable.lambda.adt.coproduct.CoProduct2;
44
import com.jnape.palatable.lambda.functor.Functor;
55

6+
import java.util.Objects;
67
import java.util.function.Function;
78

89
public abstract class NatF<A> implements Functor<A, NatF>, CoProduct2<NatF.Z<A>, NatF.S<A>> {
@@ -30,6 +31,16 @@ public <B> NatF<B> fmap(Function<? super A, ? extends B> fn) {
3031
public <R> R match(Function<? super Z<A>, ? extends R> aFn, Function<? super S<A>, ? extends R> bFn) {
3132
return aFn.apply(this);
3233
}
34+
35+
@Override
36+
public boolean equals(Object obj) {
37+
return obj instanceof Z;
38+
}
39+
40+
@Override
41+
public int hashCode() {
42+
return 31;
43+
}
3344
}
3445

3546
public static final class S<A> extends NatF<A> {
@@ -53,5 +64,10 @@ public <B> NatF<B> fmap(Function<? super A, ? extends B> fn) {
5364
public <R> R match(Function<? super Z<A>, ? extends R> aFn, Function<? super S<A>, ? extends R> bFn) {
5465
return bFn.apply(this);
5566
}
67+
68+
@Override
69+
public boolean equals(Object obj) {
70+
return obj instanceof S && Objects.equals(carrier(), ((S) obj).carrier());
71+
}
5672
}
5773
}

0 commit comments

Comments
 (0)