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

Again, this is not possible if you are a library user of Option / OptionF. The Java compiler prevents you from creating an instance of OptionF, because the constructor is private, and the only way such instance may be introduced is via the helper function in OptionF.

I think you misread my snippet: it does not build an instance of OptionF via its constructor: it simply delegate to a valid App<OptionF, A> to implement the proof method.
My snippet only use public methods from your gist, namely fromOption and toOption. Yet it produce it produce a ClassCastException.

FWIW... In higher I used a token based control access policy
https://github.com/palladin/Higher/blob/master/src/Higher.Core/CoreTypes.fs

I've been mucking around with this trick for a little while, it starts to get a bit ugly when you have more than one level of nesting of types, e.g. F<G<A>> sometimes needs to be represented as App<F, App<G, A>> and other times as App<App<F, G>, A>. You'll run into that if you try to represent Functor composition, for example.

@jbgi your project looks really interesting, thanks for sharing it. I've been purposefully ignoring the fact that a user could provide a false implementation of the type so far. I had an inkling that the casts could be made safe with a pre-processor, but hadn't looked into it yet.

@jbgi This version fixes your example:

class Option<A> {
  protected Option() { }
}
interface App<F, A> {
  F proof();
}
class OptionF  {
  private final Option<?> value;

  private OptionF(Option<?> value) {
      this.value = value;
  }

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

      public OptionF proof() {
          return new OptionF(v);
      }

    };
  }

  public static <A> Option<A> toOption(App<OptionF, A> v) {
    return (Option<A>) v.proof().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, indeed! But unfortunately this just move unsafety onto the type parameter:

    public static void main(String[] args) {
        App<OptionF, Integer> intOption = OptionF.fromOption(new Option<Integer>());
        App<OptionF, String> fakeStringOption = new App<OptionF, String>() {
            @Override
            public OptionF proof() {
                return intOption.proof();
            }
        };
        Option<String> notAstringOption = OptionF.toOption(fakeStringOption); // unsafe cast of an Option<Integer> to an Option<String> !!
    }

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