Skip to content

Commit 1760ec4

Browse files
jnapejnape
committed
adding Fix, the type corresponding to the least fixed point of a functor
1 parent b51e93f commit 1760ec4

4 files changed

Lines changed: 160 additions & 0 deletions

File tree

‎src/main/java/com/jnape/palatable/lambda/recursionschemes/Fix.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;
2+
3+
import com.jnape.palatable.lambda.functor.Functor;
4+
5+
/**
6+
* A type-level encoding of the least fixed point of a given functor; that is, given a <code>{@link
7+
* Functor}&lt;X&gt;</code> <code>f</code> and a value <code>x</code> of type <code>X</code>, <code>x</code> is the
8+
* least fixed point of <code>f</code> if, and only if, for all functions <code>fn</code>, <code>f.fmap(fn) ==
9+
* f</code>.
10+
* <p>
11+
* This encoding is foundational to the recursion schemes contained in this package, as it provides a generic,
12+
* arbitrarily deep recursive type signature corresponding to inductive and co-inductive types.
13+
* <p>
14+
* For more information, read about
15+
* <a href="https://www.schoolofhaskell.com/user/bartosz/understanding-algebras" target="_top">Fix</a>.
16+
*
17+
* @param <F> the functor unification type
18+
* @param <Unfixed> the type corresponding to the unfixed functor
19+
*/
20+
@FunctionalInterface
21+
public interface Fix<F extends Functor, Unfixed extends Functor<?, ? extends F>> {
22+
23+
/**
24+
* Unfix the currently fixed functor.
25+
*
26+
* @return the unfixed functor
27+
*/
28+
Unfixed unfix();
29+
30+
/**
31+
* Fix a {@link Functor} f.
32+
*
33+
* @param unfixed the unfixed functor
34+
* @param <F> the functor unification type
35+
* @param <Unfixed> the type corresponding to the unfixed functor
36+
* @return the fixed functor
37+
*/
38+
static <F extends Functor, Unfixed extends Functor<? extends Fix<F, ?>, F>> Fix<F, Unfixed> fix(Unfixed unfixed) {
39+
return () -> unfixed;
40+
}
41+
}
42+

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

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
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.Fix.fix;
8+
import static org.junit.Assert.assertEquals;
9+
import static testsupport.recursion.ListF.cons;
10+
import static testsupport.recursion.ListF.nil;
11+
import static testsupport.recursion.NatF.s;
12+
import static testsupport.recursion.NatF.z;
13+
14+
public class FixTest {
15+
16+
@Test
17+
@SuppressWarnings("unused")
18+
public void validTypeSafeSignatures() {
19+
Fix<NatF, NatF<Fix<NatF, NatF<Fix<NatF, NatF<Fix<NatF, ?>>>>>>> losslessNatF = fix(s(fix(s(fix(z())))));
20+
Fix<NatF, NatF<Fix<NatF, ?>>> compactNatF = fix(s(fix(s(fix(z())))));
21+
Fix<NatF, ?> minimalNatF = fix(s(fix(s(fix(z())))));
22+
23+
Fix<ListF<Integer, ?>, ListF<Integer, Fix<ListF<Integer, ?>, ListF<Integer, Fix<ListF<Integer, ?>, ListF<Integer, Fix<ListF<Integer, ?>, ListF<Integer, Fix<ListF<Integer, ?>, ?>>>>>>>>> losslessListF = fix(cons(3, fix(cons(2, fix(cons(1, fix(nil())))))));
24+
Fix<ListF<Integer, ?>, ListF<Integer, Fix<ListF<Integer, ?>, ?>>> compactListF = fix(cons(3, fix(cons(2, fix(cons(1, fix(nil())))))));
25+
Fix<ListF<Integer, ?>, ?> minimalListF = fix(cons(3, fix(cons(2, fix(cons(1, fix(nil())))))));
26+
}
27+
28+
@Test
29+
public void fixAndUnfix() {
30+
NatF<Fix<NatF, ?>> z = z();
31+
assertEquals(z, fix(z).unfix());
32+
}
33+
}

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

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package testsupport.recursion;
2+
3+
import com.jnape.palatable.lambda.functor.Functor;
4+
5+
import java.util.function.Function;
6+
7+
public abstract class ListF<A, B> implements Functor<B, ListF<A, ?>> {
8+
9+
public static <A, B> ListF<A, B> nil() {
10+
return new Nil<>();
11+
}
12+
13+
public static <A, B> ListF<A, B> cons(@SuppressWarnings("unused") A a,
14+
@SuppressWarnings("unused") B b) {
15+
return new Cons<>();
16+
}
17+
18+
public static final class Nil<A, B> extends ListF<A, B> {
19+
20+
@Override
21+
@SuppressWarnings("unchecked")
22+
public <C> ListF<A, C> fmap(Function<? super B, ? extends C> fn) {
23+
return (Nil<A, C>) this;
24+
}
25+
}
26+
27+
public static final class Cons<A, B> extends ListF<A, B> {
28+
29+
@Override
30+
@SuppressWarnings("unchecked")
31+
public <C> ListF<A, C> fmap(Function<? super B, ? extends C> fn) {
32+
return (ListF<A, C>) this;
33+
}
34+
}
35+
}

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

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package testsupport.recursion;
2+
3+
import com.jnape.palatable.lambda.adt.coproduct.CoProduct2;
4+
import com.jnape.palatable.lambda.functor.Functor;
5+
6+
import java.util.function.Function;
7+
8+
public abstract class NatF<A> implements Functor<A, NatF>, CoProduct2<NatF.Z<A>, NatF.S<A>> {
9+
10+
public static <A> NatF<A> z() {
11+
return new Z<>();
12+
}
13+
14+
public static <A> NatF<A> s(@SuppressWarnings("unused") A a) {
15+
return new S<>();
16+
}
17+
18+
public static final class Z<A> extends NatF<A> {
19+
20+
private Z() {
21+
}
22+
23+
@Override
24+
@SuppressWarnings("unchecked")
25+
public <B> NatF<B> fmap(Function<? super A, ? extends B> fn) {
26+
return (NatF<B>) this;
27+
}
28+
29+
@Override
30+
public <R> R match(Function<? super Z<A>, ? extends R> aFn, Function<? super S<A>, ? extends R> bFn) {
31+
return aFn.apply(this);
32+
}
33+
}
34+
35+
public static final class S<A> extends NatF<A> {
36+
private S() {
37+
}
38+
39+
@Override
40+
@SuppressWarnings("unchecked")
41+
public <B> NatF<B> fmap(Function<? super A, ? extends B> fn) {
42+
return (NatF<B>) this;
43+
}
44+
45+
@Override
46+
public <R> R match(Function<? super Z<A>, ? extends R> aFn, Function<? super S<A>, ? extends R> bFn) {
47+
return bFn.apply(this);
48+
}
49+
}
50+
}

0 commit comments

Comments
 (0)