Support for higher-kinded types

[mkjpryor]

Bit of a blue-sky feature request, but I was just wondering if Hack might ever support higher-kinded types? Since we already have a good lambda syntax and type inference, higher-kinded types would put Hack almost on a par with Scala for hybrid functional/object-oriented programming, but with a more familiar syntax for PHP/Java/C# programmers.

The only syntax change I envisage it requiring is a wildcard for generic types. Since types are erased at runtime, it wouldn't require any runtime changes (other than to strip the new syntax), however the type-checker would be (much) harder...! It would allow us to do some pretty fancy stuff with container types, even down to defining a type-safe monad. I envisage it looking something like this:

<?hh // strict

trait Monad<T, TMonad<?>> {
    public abstract function flatMap<TTo>((function(T): TMonad<TTo>) $f): TMonad<TTo>;

    public static abstract function unit<TTo>(TTo $x): TMonad<TTo>;

    public function map<TTo>((function(T): TTo) $f): TMonad<TTo> {
        return $this->flatMap($x ==> static::unit($f($x)));
    }
}

final class Maybe<T> {
    use Monad<T, Maybe<?>>;

    // null indicates an "empty" maybe
    private function __construct(private ?T $value) {}

    public abstract function flatMap<TTo>((function(T): Maybe<TTo>) $f): Maybe<TTo> {
        return $this->value === null ? Maybe::none() : $f($this->value);
    }

    public static function unit<TTo>(TTo $x): Maybe<TTo> {
        return Maybe::just($x);
    }

    public static function just<TTo>(TTo $x): Maybe<TTo> {
        return new Maybe($x);
    }

    public static function none<TTo>(): Maybe<TTo> {
        // We could optimise this using UNSAFE to have a single none instance...
        return new Maybe(null);
    }
}

final class MonadOps {
    public static function lift<TMonad<?>, T, TTo>((function(T): TTo) $f): (function(TMonad<T>): TMonad<TTo>) {
        return $x ==> $x->map($f);
    }
}

[jwatzman]

While we do want to expand our generics syntax at some point, I don't think anything involving higher kinds is on our roadmap :) cc @paroski and @pikatchu if they have any comments.

[jwatzman]

(Though of course if you are interested in implementing something yourself, let us know and we can chat about the language design and implementation considerations.)

[mkjpryor]

I did think it was probably a bit out there - just thought I'd ask.

I would be interested in trying to implement something - I've never worked on anything like a static verifier or virtual machine before, so wouldn't really know where to start, but I am definitely interested in learning... On 2 Jun 2014 20:30, "Josh Watzman" notifications@github.com wrote:

(Though of course if you are interested in implementing something yourself, let us know and we can chat about the language design and implementation considerations.)

— Reply to this email directly or view it on GitHub https://github.com/facebook/hhvm/issues/2825#issuecomment-44880272.

[paulbiss]

cc @dlreeves @andrewjkennedy

This is a pretty old feature request but it sounds like the kind of thing you guys might be interested in.

[blast-hardcheese]

Necro :+1:!

[relrod]

Another vote for this. :)