Last active
January 9, 2019 11:23
-
-
Save jdegoes/6842d471e7b8849f90d5bb5644ecb3b2 to your computer and use it in GitHub Desktop.
Modeling higher-kinded types in a language without them.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Option<A> { | |
protected Option() { } | |
} | |
interface App<F, A> { | |
F proof(); | |
} | |
class OptionF { | |
private OptionF() {} | |
private static class AppOption<A> implements App<OptionF, A> { | |
public final Option<A> value; | |
AppOption(Option<A> value) { | |
this.value = value; | |
} | |
public OptionF proof() { | |
return new OptionF(); | |
} | |
} | |
public static <A> App<OptionF, A> fromOption(Option<A> v) { | |
return new AppOption(v); | |
} | |
public static <A> Option<A> toOption(App<OptionF, A> v) { | |
return (((AppOption<A>)v).value); | |
} | |
} | |
interface Function<A, B> { | |
B apply(A a); | |
} | |
interface Functor<F> { | |
<A, B> App<F, B> map(Function<A, B> f, App<F, A> fa); | |
} |
OK, I'm not going to claim it's pretty... 😆
public class Test {
public static void main(String[] args) {
String result = OptionModule.inject(new OptionConsumer<String>() {
public <OptionF> String consume(OptionModule<OptionF> provider) {
Option<Integer> answer = Option.some(42);
App<OptionF, Integer> answerF = provider.fromOption(answer);
App<OptionF, String> answer2 = provider.functor().map(new Function<Integer, String>() { public String apply(Integer i) { return i.toString(); } }, answerF);
return provider.toOption(answer2).getOrElse("");
}
});
System.out.println(result);
}
}
interface Function<A, B> {
B apply(A a);
}
abstract class Option<A> {
private Option() { }
public A getOrElse(A def) {
return fold(def, new Function<A, A>() { public A apply(A a) { return a; } });
}
public static <A> Option<A> none() {
return new Option<A>() {
public <Z> Z fold(Z none, Function<A, Z> some) {
return none;
}
};
}
public static <A> Option<A> some(A a) {
return new Option<A>() {
public <Z> Z fold(Z none, Function<A, Z> some) {
return some.apply(a);
}
};
}
public abstract <Z> Z fold(Z none, Function<A, Z> some);
}
interface App<F, A> { }
interface Functor<F> {
<A, B> App<F, B> map(Function<A, B> f, App<F, A> fa);
}
interface OptionConsumer<Z> {
<OptionF> Z consume(OptionModule<OptionF> provider);
}
class OptionModule<OptionF> {
private OptionModule() { }
public <A> App<OptionF, A> fromOption(Option<A> v) {
return new AppOption<A>(v);
}
public <A> Option<A> toOption(App<OptionF, A> v) {
return (((AppOption<A>)v).value);
}
public Functor<OptionF> functor() {
return new Functor<OptionF>() {
public <A, B> App<OptionF, B> map(Function<A, B> f, App<OptionF, A> fa) {
Option<A> o1 = toOption(fa);
return fromOption(o1.fold(Option.none(), new Function<A, Option<B>>() { public Option<B> apply(A a) { return Option.some(f.apply(a)); } }));
}
};
}
public static <Z> Z inject(OptionConsumer<Z> consumer) {
return consumer.consume(new OptionModule<OptionFTag>());
}
private class AppOption<A> implements App<OptionF, A> {
public final Option<A> value;
AppOption(Option<A> value) {
this.value = value;
}
}
private static class OptionFTag { private OptionFTag() { } }
}
@jdegoes, this one was easy 😄
public static void main(String[] args) {
OptionModule.inject(new OptionConsumer<String>() {
public <OptionF> String consume(OptionModule<OptionF> provider) {
provider.toOption(new App<OptionF, String>() {}); // ClassCastException
return "";
}
});
}
@TomasMikula even if it is obscure, if that does not impact client code and code can be generated it could have been a good solution.
A simple modification renders the original "safe up to null", again:
class Option<A> {
protected Option() { }
}
abstract class App<F, A> {
protected F proof();
}
class OptionF {
private OptionF() {}
private static class AppOption<A> extends App<OptionF, A> {
public final Option<A> value;
AppOption(Option<A> value) {
this.value = value;
}
protected OptionF proof() {
return new OptionF();
}
}
public static <A> App<OptionF, A> fromOption(Option<A> v) {
return new AppOption(v);
}
public static <A> Option<A> toOption(App<OptionF, A> v) {
return (((AppOption<A>)v).value);
}
}
interface Function<A, B> {
B apply(A a);
}
interface Functor<F> {
<A, B> App<F, B> map(Function<A, B> f, App<F, A> fa);
}
@jdegoes, I don't think so. My original counter-example still produce a ClassCastException:
https://gist.github.com/jdegoes/6842d471e7b8849f90d5bb5644ecb3b2#gistcomment-1818237
Damn access methods. If only Java had protected[this]
! Or an abstract private method that could be implemented and seen only by subclasses...
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@TomasMikula: It looks like a good solution... but only for data types with 1 type parameters. A major problem with encoding of hkt that make use F-Bounded polymorphism is that it does not scale well to multiple type parameters: you would have to create a new, independent interfaces
AppX
for each data types of X type parameters, becauseApp2
cannot extendsApp
(due to the F-Bounded constraint). Eg.Then how to retrieve an
App
from anApp2
(eg. to make use forFunctor
) without giving up information on type parameters ?? I tried something like:While it appears to works (very verbosely) until then, it stops to works as soon as you try to use something like a
BiFunctor
on an App2: then you lost information on the first type parameter ofApp2
, and with it, the ability to retrieve a usefulApp
from theApp2
.The encoding in https://github.com/derive4j/hkt/blob/master/src/main/java/org/derive4j/hkt/__2.java does not have this problem:
App2
simply extendsApp
.And since the annotation processor is packaged with the library providing the
AppX
interfaces (named__X
), type-safety will be ensured as long as the user does not explicitly deactivate annotation processing (which I would qualified as malicious/intentional in the same sense as my specially crafted counter-examples).