Modeling higher-kinded types in a language without them.

HigherKindedJava.java

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);
}

@jbgi Ah, you're right! Thanks for being so patient. 🙏

Although, I'd point out the following: this is not accidental type unsafety, but malicious type unsafety, in the sense that, a user would have to intentionally work around the limited options for constructing OptionF.

I have another idea to fix this loophole by moving closer to the paper, representing an existential type via skolemization, and forcing delimited modules on the user... I'll give it a try this weekend and post back.

@jbgi Ah yeah. Second attempt:

class Option<A> {
  protected Option() { }
}
interface App<F, A, Self extends App<F, A, Self>> {
  <T> T accept(Function<App<F, A, ? extends F>, T> f);
}
class OptionF  {
  private OptionF() {}

  private static class AppOption<A> extends OptionF implements App<OptionF, A, AppOption<A>> {
    public final Option<A> value;

    AppOption(Option<A> value) {
      this.value = value;
    }

    public <T> T accept(Function<App<OptionF, A, ? extends OptionF>, T> f) {
      return f.apply(this);
    }
  }

  public static <A> App<OptionF, A, ?> fromOption(Option<A> v) {
    return new AppOption<A>(v);
  }

  public static <A> Option<A> toOption(App<OptionF, A, ?> v) {
    return v.accept(app -> (AppOption<A>) app).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);
}

Well, this one is harder. But once you start using F-bounded polymorphism in conjunction with parametric polymorphism then they are cases where the compiler just accept anything, like this one:

  public static void main(String[] args) {
    App<OptionF, String, ?> fake = fake();
    OptionF.toOption(fake); // ClassCastException
  }

  static <A, F extends OptionF & App<OptionF, A, F>> App<OptionF, A, F> fake() {
    return new App<OptionF, A, F>() {
      @Override public <T> T accept(Function<App<OptionF, A, ? extends OptionF>, T> f) {
        return f.apply(this);
      }
    };
  }

Interesting. One more try 😄. The difference here is addition of method

Self self();

to the App interface.

class Option<A> {
  protected Option() { }
}
interface App<F, A, Self extends App<F, A, Self>> {
  <T> T accept(Function<App<F, A, ? extends F>, T> f);
  Self self();
}
class OptionF  {
  private OptionF() {}

  private static class AppOption<A> extends OptionF implements App<OptionF, A, AppOption<A>> {
    public final Option<A> value;

    AppOption(Option<A> value) {
      this.value = value;
    }

    public <T> T accept(Function<App<OptionF, A, ? extends OptionF>, T> f) {
      return f.apply(this);
    }

    public AppOption<A> self() {
      return this;
    }
  }

  public static <A> App<OptionF, A, ?> fromOption(Option<A> v) {
    return new AppOption<A>(v);
  }

  public static <A> Option<A> toOption(App<OptionF, A, ?> v) {
    return v.self().accept(app -> (AppOption<A>) app).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);
}

@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, because App2 cannot extends App (due to the F-Bounded constraint). Eg.

interface App2<F, A, B, Self extends App2<F, A, B, Self>> {
  <T> T accept2(Function<App2<F, A, B, ? extends F>, T> f);
  Self self2();
}

Then how to retrieve an App from an App2 (eg. to make use for Functor) without giving up information on type parameters ?? I tried something like:

interface App2<F, F2, A, B, Self extends App2<F, F2, A, B, Self>> {
  <T> T accept(Function<App2<F, F2, A, B, ? extends F2>, T> f);
  Self self();
  App<F, B, ?> toApp();
}

class EitherF<A> {
  private EitherF() {}
  private static class AppEither<A, B> extends EitherF<A> implements App<EitherF<A>, B, EitherF.AppEither<A, B>> {
    public final Either<A, B> value;
    AppEither(Either<A, B> value) {
      this.value = value;
    }
    @Override public <T> T accept(Function<App<EitherF<A>, B, ? extends EitherF<A>>, T> f) {
      return f.apply(this);
    }
    @Override public AppEither<A, B> self() {
      return this;
    }
  }

  static class EitherF2 {
    private EitherF2() { }
    private static class App2Either<A, B> extends EitherF2 implements App2<EitherF<A>, EitherF2, A, B, EitherF2.App2Either<A, B>> {
      public final Either<A, B> value;
      App2Either(Either<A, B> value) {
        this.value = value;
      }
      @Override public <T> T accept(Function<App2<EitherF<A>, EitherF2, A, B, ? extends EitherF2>, T> f) {
        return f.apply(this);
      }
      @Override public EitherF2.App2Either<A, B> self() {
        return this;
      }
      @Override public App<EitherF<A>, B, ?> toApp() {
        return new EitherF.AppEither<>(value);
      }
    }
  }
  public static <A, B> App2<EitherF<A>, EitherF2, A, B, ?> fromEither(Either<A, B> v) {
    return new EitherF2.App2Either<A, B>(v);
  }
  public static <A, B> Either<A, B> toEither(App2<?, EitherF2, A, B, ?>  v) {
    return v.self().accept(app -> (EitherF2.App2Either<A, B>) app).value;
  }
  public static <A, B> Either<A, B> toEither(App<EitherF<A>, B, ?>  v) {
    return v.self().accept(app -> (EitherF.AppEither<A, B>) app).value;
  }
}

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 of App2, and with it, the ability to retrieve a useful App from the App2.

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 extends App.
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).

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() { } }
}

@jbgi I never meant to suggest anyone should use that, it is really obscure. I was just trying if I could make it safe. I find @jdegoes's solution much cleaner (no F-bounds), although all the client code has to be written as a consumer of OptionModule.

@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...