New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support higher kinded type #30

Open
fdecampredon opened this Issue Nov 18, 2014 · 20 comments

Comments

Projects
None yet
@fdecampredon

fdecampredon commented Nov 18, 2014

example :

interface Mappable<M<A>>  {
  map<B>(func: (a:A) => B): M<B>;
}

@fdecampredon fdecampredon changed the title from Support high kinded type to Support higher kinded type Nov 18, 2014

@wizzard0

This comment has been minimized.

Show comment
Hide comment
@wizzard0

wizzard0 commented Nov 18, 2014

👍

@avikchaudhuri

This comment has been minimized.

Show comment
Hide comment
@avikchaudhuri

avikchaudhuri Nov 18, 2014

Contributor

Interesting. We have some ideas on how we can generalize type aliases to model higher kinds in the future; but I'm curious if you already have some concrete examples that you need this feature to type check.

Contributor

avikchaudhuri commented Nov 18, 2014

Interesting. We have some ideas on how we can generalize type aliases to model higher kinds in the future; but I'm curious if you already have some concrete examples that you need this feature to type check.

@fdecampredon

This comment has been minimized.

Show comment
Hide comment
@fdecampredon

fdecampredon Nov 19, 2014

the mappable interface is pretty much the kind of interface that I'd like to use.
simple example:

interface List<A> extends Mappable<List<A>> {
  ....
  // so we have  map<B>(func: (a:A) => B): List<B>;
}

interface Sequence<A> extends Mappable<Sequence<A>> {
  ....
  // so we have  map<B>(func: (a:A) => B): Sequence<B>;
}

function map<M,A,B>(mappable: Mappable<M<A>>, func: (a:A) => B): M<B> {
  return mappable.map(func)
}

function  mapLenghth<M>(mappable: Mappable<M<{length : number}>>): M<number> {
  return mappable.map(mappable, a => a.length);
}

var list: List<string>;
var lengthList = mapLength(list); // List<number>

var sequence: Sequence<string>;
var lengthSeq = mapLength(sequence); // Sequence<number>

var array: Array<string>;
var lengthArray = mapLength(array); // Array<number> since in fact 
                                    // Array<A> implements Mappable<Array<A>> 
//etc...

Note that in this example we always have mappable mapping to their own type, but we could have for example :

class Sequence<A> implements Mappable<Array<A>> {
  map<B>(func: (a:A) => B): Array<B> {
    return Array.from(...this, func);
  }
}

fdecampredon commented Nov 19, 2014

the mappable interface is pretty much the kind of interface that I'd like to use.
simple example:

interface List<A> extends Mappable<List<A>> {
  ....
  // so we have  map<B>(func: (a:A) => B): List<B>;
}

interface Sequence<A> extends Mappable<Sequence<A>> {
  ....
  // so we have  map<B>(func: (a:A) => B): Sequence<B>;
}

function map<M,A,B>(mappable: Mappable<M<A>>, func: (a:A) => B): M<B> {
  return mappable.map(func)
}

function  mapLenghth<M>(mappable: Mappable<M<{length : number}>>): M<number> {
  return mappable.map(mappable, a => a.length);
}

var list: List<string>;
var lengthList = mapLength(list); // List<number>

var sequence: Sequence<string>;
var lengthSeq = mapLength(sequence); // Sequence<number>

var array: Array<string>;
var lengthArray = mapLength(array); // Array<number> since in fact 
                                    // Array<A> implements Mappable<Array<A>> 
//etc...

Note that in this example we always have mappable mapping to their own type, but we could have for example :

class Sequence<A> implements Mappable<Array<A>> {
  map<B>(func: (a:A) => B): Array<B> {
    return Array.from(...this, func);
  }
}
@metaweta

This comment has been minimized.

Show comment
Hide comment
@metaweta

metaweta Nov 21, 2014

It's necessary for defining monads (a special kind of mappable):

interface Monad<A, M<>> {
  static map<B>(f:(a:A) => B): M<A> => M<B>;
  static lift(a:A): M<A>;
  static join(mma: M<M<A>>): M<A>;
}

Basically any collection type (even an asynchronous collection like a stream) implements the monad interface; so do parsers, promises, membranes, encapsulated state (particularly useful for serialized computations), and many more design patterns.

Here's code for how one could implement the standard list monad. This particular monad is clunky because it's already built into javascript with special syntax, but the other features above turn out particularly nicely using this interface.

class ArrayMonad<A> implements Monad<A, Array> {
  static map<B>(f:(a:A) => B): Array<A> => Array<B> {
    return function (arr: Array<A>): Array<B> {
      return arr.map(f);
    };
  }
  static lift(a:A): Array<A> { return [a]; }
  static join(mma: Array<Array<A>>): Array<A> {
    var result: Array<A> = [];
    var len = mma.length;
    for (var i = 0; i < len; ++i) {
      result = result.concat(mma[i]);
    }
  }
}

ArrayMonad.map((x)=>''+x+x)([1,2,3,4]); // ['11','22','33','44']
ArrayMonad.lift(5); // [5]
ArrayMonad.join([[1,2,3],[4,5],[],[6]]); // [1,2,3,4,5,6]

Another example:

interface Cartesian<T, F<>> {
  function all(arr: Array<F<T>>): F<Array<T>>;
}

class PromiseCartesian<T> implements Cartesian<T, Promise> {
  function all(arr: Array<Promise<T>>): Promise<Array<T>> {
    // return a promise that resolves once all the promises in arr have resolved
  }
}

class MaybeCartesian<T> implements Cartesian<T, ?> {
  // If all the elements of arr are non-null, returns arr; otherwise returns null.
  function all(arr: Array<?T>): ?Array<T> {
    var len = arr.length;
    var result:Array<T> = [];
    for (var i = 0; i < len; ++i) {
      if (arr[i] == null) { return null; }
      result.push(arr[i]);
    }
    return result;
  }
}

metaweta commented Nov 21, 2014

It's necessary for defining monads (a special kind of mappable):

interface Monad<A, M<>> {
  static map<B>(f:(a:A) => B): M<A> => M<B>;
  static lift(a:A): M<A>;
  static join(mma: M<M<A>>): M<A>;
}

Basically any collection type (even an asynchronous collection like a stream) implements the monad interface; so do parsers, promises, membranes, encapsulated state (particularly useful for serialized computations), and many more design patterns.

Here's code for how one could implement the standard list monad. This particular monad is clunky because it's already built into javascript with special syntax, but the other features above turn out particularly nicely using this interface.

class ArrayMonad<A> implements Monad<A, Array> {
  static map<B>(f:(a:A) => B): Array<A> => Array<B> {
    return function (arr: Array<A>): Array<B> {
      return arr.map(f);
    };
  }
  static lift(a:A): Array<A> { return [a]; }
  static join(mma: Array<Array<A>>): Array<A> {
    var result: Array<A> = [];
    var len = mma.length;
    for (var i = 0; i < len; ++i) {
      result = result.concat(mma[i]);
    }
  }
}

ArrayMonad.map((x)=>''+x+x)([1,2,3,4]); // ['11','22','33','44']
ArrayMonad.lift(5); // [5]
ArrayMonad.join([[1,2,3],[4,5],[],[6]]); // [1,2,3,4,5,6]

Another example:

interface Cartesian<T, F<>> {
  function all(arr: Array<F<T>>): F<Array<T>>;
}

class PromiseCartesian<T> implements Cartesian<T, Promise> {
  function all(arr: Array<Promise<T>>): Promise<Array<T>> {
    // return a promise that resolves once all the promises in arr have resolved
  }
}

class MaybeCartesian<T> implements Cartesian<T, ?> {
  // If all the elements of arr are non-null, returns arr; otherwise returns null.
  function all(arr: Array<?T>): ?Array<T> {
    var len = arr.length;
    var result:Array<T> = [];
    for (var i = 0; i < len; ++i) {
      if (arr[i] == null) { return null; }
      result.push(arr[i]);
    }
    return result;
  }
}
@samwgoldman

This comment has been minimized.

Show comment
Hide comment
@samwgoldman

samwgoldman Mar 1, 2015

Member

Here's another code dump that aligns more closely with the syntax we have now.

type Monoid<T> = {
  zero: T;
  append: (a: T, b: T) => T;
}

// These are fine
var sumMonoid: Monoid<number> = {
  zero: 0,
  append: (a, b) => a + b
}

var productMonoid: Monoid<number> = {
  zero: 1,
  append: (a, b) => a * b
}

// The type variable T can't be free, but this
// formulation is valid for any type T.
var arrayMonoid: Monoid<Array<T>> = {
  zero: [],
  append: (a, b) => a.concat(b)
}

// We should be able to use any type, not just
// built-ins.
type Transformation<T> = (x: T) => T;
var transformationMonoid: Monoid<Transformation<T>> = {
  zero: (x) => x,
  append: (f, g) => (x) => f(g(x))
}

// HKT use case
function concat<T>(array: Array<T>, monoid: Monoid<T>): T {
  return array.reduce(monoid.append, monoid.zero);
}

var ex1: number = concat([1, 2, 3], sumMonoid);
var ex2: number = concat([1, 2, 3], productMonoid);
var ex3: Array<number> = concat([[1, 2], [3, 4]], arrayMonoid);
var ex4: Transformation<number> = concat([(x) => x + 1, (x) => x - 1], transformationMonoid);

Note that these "type classes" are a bit more cumbersome to use than they would be in Haskell, where the compiler will thread the dictionaries around for you, or Scala where the implicit rules will do the same.

Member

samwgoldman commented Mar 1, 2015

Here's another code dump that aligns more closely with the syntax we have now.

type Monoid<T> = {
  zero: T;
  append: (a: T, b: T) => T;
}

// These are fine
var sumMonoid: Monoid<number> = {
  zero: 0,
  append: (a, b) => a + b
}

var productMonoid: Monoid<number> = {
  zero: 1,
  append: (a, b) => a * b
}

// The type variable T can't be free, but this
// formulation is valid for any type T.
var arrayMonoid: Monoid<Array<T>> = {
  zero: [],
  append: (a, b) => a.concat(b)
}

// We should be able to use any type, not just
// built-ins.
type Transformation<T> = (x: T) => T;
var transformationMonoid: Monoid<Transformation<T>> = {
  zero: (x) => x,
  append: (f, g) => (x) => f(g(x))
}

// HKT use case
function concat<T>(array: Array<T>, monoid: Monoid<T>): T {
  return array.reduce(monoid.append, monoid.zero);
}

var ex1: number = concat([1, 2, 3], sumMonoid);
var ex2: number = concat([1, 2, 3], productMonoid);
var ex3: Array<number> = concat([[1, 2], [3, 4]], arrayMonoid);
var ex4: Transformation<number> = concat([(x) => x + 1, (x) => x - 1], transformationMonoid);

Note that these "type classes" are a bit more cumbersome to use than they would be in Haskell, where the compiler will thread the dictionaries around for you, or Scala where the implicit rules will do the same.

@popham

This comment has been minimized.

Show comment
Hide comment
@popham

popham Apr 29, 2015

Contributor

Oddball edge case. Given I:

interface I {
  method(): string;
  static sMethod(): string;
}

should the following error out?

class A implements I {
  method: void => string;
  static sMethod: void => string;
  constructor() {
    this.method = function () { return 5; } // NG
  }
}
A.sMethod = function () { return "peep"; }
Contributor

popham commented Apr 29, 2015

Oddball edge case. Given I:

interface I {
  method(): string;
  static sMethod(): string;
}

should the following error out?

class A implements I {
  method: void => string;
  static sMethod: void => string;
  constructor() {
    this.method = function () { return 5; } // NG
  }
}
A.sMethod = function () { return "peep"; }
@samwgoldman

This comment has been minimized.

Show comment
Hide comment
@samwgoldman

samwgoldman Apr 29, 2015

Member

@popham I'm not sure how that is related to HKT. Can you elaborate?

Member

samwgoldman commented Apr 29, 2015

@popham I'm not sure how that is related to HKT. Can you elaborate?

@popham

This comment has been minimized.

Show comment
Hide comment
@popham

popham Apr 29, 2015

Contributor

Off-topic. Apologies. (I'm imagineering what interface should look like, and this is the only lead I could find. I just went to delete the prior, but then I saw your response.)

Contributor

popham commented Apr 29, 2015

Off-topic. Apologies. (I'm imagineering what interface should look like, and this is the only lead I could find. I just went to delete the prior, but then I saw your response.)

@rockymadden

This comment has been minimized.

Show comment
Hide comment
@rockymadden

rockymadden May 5, 2015

Looking for this feature as well.

rockymadden commented May 5, 2015

Looking for this feature as well.

@isiahmeadows

This comment has been minimized.

Show comment
Hide comment
@isiahmeadows

isiahmeadows May 6, 2015

Higher order types should also include recursive types. This would help in cases like Lodash's flatten.

type Flattenable<A> = Array<A> | Array<Flattenable<A>>;

declare function flatten<T>(list: Flattenable<T>): Array<T>;

isiahmeadows commented May 6, 2015

Higher order types should also include recursive types. This would help in cases like Lodash's flatten.

type Flattenable<A> = Array<A> | Array<Flattenable<A>>;

declare function flatten<T>(list: Flattenable<T>): Array<T>;
@samwgoldman

This comment has been minimized.

Show comment
Hide comment
@samwgoldman

samwgoldman May 6, 2015

Member

@popham Your example isn't really related to HKT either. Also, recursive types should work. I think your type definition is wrong. You probably want something like this:

type Flattenable<A> = Array<A | Flattenable<A>>;
var foo: Flattenable<string> = ['a', ['a'], [['a']]]; // OK
Member

samwgoldman commented May 6, 2015

@popham Your example isn't really related to HKT either. Also, recursive types should work. I think your type definition is wrong. You probably want something like this:

type Flattenable<A> = Array<A | Flattenable<A>>;
var foo: Flattenable<string> = ['a', ['a'], [['a']]]; // OK
@samwgoldman

This comment has been minimized.

Show comment
Hide comment
@samwgoldman

samwgoldman May 6, 2015

Member

Also, for what it's worth. Using the existential types that are on master right now, my previous example with 2 character substitutions type checks:

/* @flow */

type Monoid<T> = {
  zero: T;
  append: (a: T, b: T) => T;
}

// These are fine
var sumMonoid: Monoid<number> = {
  zero: 0,
  append: (a, b) => a + b
}

var productMonoid: Monoid<number> = {
  zero: 1,
  append: (a, b) => a * b
}

var arrayMonoid: Monoid<Array<*>> = {
  zero: [],
  append: (a, b) => a.concat(b)
}

type Transformation<T> = (x: T) => T;
var transformationMonoid: Monoid<Transformation<*>> = {
  zero: (x) => x,
  append: (f, g) => (x) => f(g(x))
}

// HKT use case (edit: not actually HKT)
function concat<T>(array: Array<T>, monoid: Monoid<T>): T {
  return array.reduce(monoid.append, monoid.zero);
}

var ex1: number = concat([1, 2, 3], sumMonoid);
var ex2: number = concat([1, 2, 3], productMonoid);
var ex3: Array<number> = concat([[1, 2], [3, 4]], arrayMonoid);
var ex4: Transformation<number> = concat([(x) => x + 1, (x) => x - 1], transformationMonoid);
Member

samwgoldman commented May 6, 2015

Also, for what it's worth. Using the existential types that are on master right now, my previous example with 2 character substitutions type checks:

/* @flow */

type Monoid<T> = {
  zero: T;
  append: (a: T, b: T) => T;
}

// These are fine
var sumMonoid: Monoid<number> = {
  zero: 0,
  append: (a, b) => a + b
}

var productMonoid: Monoid<number> = {
  zero: 1,
  append: (a, b) => a * b
}

var arrayMonoid: Monoid<Array<*>> = {
  zero: [],
  append: (a, b) => a.concat(b)
}

type Transformation<T> = (x: T) => T;
var transformationMonoid: Monoid<Transformation<*>> = {
  zero: (x) => x,
  append: (f, g) => (x) => f(g(x))
}

// HKT use case (edit: not actually HKT)
function concat<T>(array: Array<T>, monoid: Monoid<T>): T {
  return array.reduce(monoid.append, monoid.zero);
}

var ex1: number = concat([1, 2, 3], sumMonoid);
var ex2: number = concat([1, 2, 3], productMonoid);
var ex3: Array<number> = concat([[1, 2], [3, 4]], arrayMonoid);
var ex4: Transformation<number> = concat([(x) => x + 1, (x) => x - 1], transformationMonoid);
@pmlt

This comment has been minimized.

Show comment
Hide comment
@pmlt

pmlt Mar 16, 2016

Any update regarding this feature? There was no response within 30 days yet this feature request is not yet closed. I'd also like to see this become reality.

pmlt commented Mar 16, 2016

Any update regarding this feature? There was no response within 30 days yet this feature request is not yet closed. I'd also like to see this become reality.

@gcanti

This comment has been minimized.

Show comment
Hide comment
@gcanti

gcanti Sep 5, 2016

Here's a (hacky) way to implement HKT: https://github.com/gcanti/flow-static-land

gcanti commented Sep 5, 2016

Here's a (hacky) way to implement HKT: https://github.com/gcanti/flow-static-land

@jeffmo

This comment has been minimized.

Show comment
Hide comment
@jeffmo

jeffmo Sep 9, 2016

Member

Thanks, @gcanti -- that seems like a reasonable workaround for now.

Just to follow up with something semi-official: There's a chance we may get to this at some point, but it's not on the near-term horizon for the core team. As we've done so far with this, we'll leave this issue open to track the request for if/when this surfaces the priority queue.

Member

jeffmo commented Sep 9, 2016

Thanks, @gcanti -- that seems like a reasonable workaround for now.

Just to follow up with something semi-official: There's a chance we may get to this at some point, but it's not on the near-term horizon for the core team. As we've done so far with this, we'll leave this issue open to track the request for if/when this surfaces the priority queue.

@Jacse

This comment has been minimized.

Show comment
Hide comment
@Jacse

Jacse Jan 13, 2017

Is there still no way to do this "officially"?

Jacse commented Jan 13, 2017

Is there still no way to do this "officially"?

@jasonkuhrt

This comment has been minimized.

Show comment
Hide comment
@jasonkuhrt

jasonkuhrt Nov 10, 2017

@jeffmo In the year+ since your last comment, how has thinking on this by the core team changed if at all?

jasonkuhrt commented Nov 10, 2017

@jeffmo In the year+ since your last comment, how has thinking on this by the core team changed if at all?

@astampoulis

This comment has been minimized.

Show comment
Hide comment
@astampoulis

astampoulis Nov 23, 2017

From what I can tell, higher-kinded types are actually supported in Flow, though they are encoded using the simple-kinded function type and the utility type $Call for type-level application. In fact, some of the utility types of Flow are using this encoding, such as the $ObjMap<T, F> type, where F is higher-kinded. Maybe this isn't official though, because I don't see it explicitly mentioned in the documentation, or I might be missing something.

The encoding is as follows:
the kind Type -> Type is encoded as the type Function
the type-level function λA.F(A) is encoded as the type <A>(A) => F(...A...)
the type-level application F T is encoded as the type $Call<F, T>
the conversion-rule is not fully supported, so some times you have to explicitly use an intermediate cast to any to view a variable of type $Call<F, T> as having the type of the β-redex F[T], so for example if we have type F = <A>(A) => Array<A>, a variable of type $Call<F, string> is not immediately typeable as Array<string>. The conversion rule is used for expressions though, so that part is type-safe. Actually this seems to work right.

Not sure if there is a way to encode kinds like (Type -> Type) -> Type (e.g. for monads), maybe by using a more restricted type than Function to encode the higher kinds.

astampoulis commented Nov 23, 2017

From what I can tell, higher-kinded types are actually supported in Flow, though they are encoded using the simple-kinded function type and the utility type $Call for type-level application. In fact, some of the utility types of Flow are using this encoding, such as the $ObjMap<T, F> type, where F is higher-kinded. Maybe this isn't official though, because I don't see it explicitly mentioned in the documentation, or I might be missing something.

The encoding is as follows:
the kind Type -> Type is encoded as the type Function
the type-level function λA.F(A) is encoded as the type <A>(A) => F(...A...)
the type-level application F T is encoded as the type $Call<F, T>
the conversion-rule is not fully supported, so some times you have to explicitly use an intermediate cast to any to view a variable of type $Call<F, T> as having the type of the β-redex F[T], so for example if we have type F = <A>(A) => Array<A>, a variable of type $Call<F, string> is not immediately typeable as Array<string>. The conversion rule is used for expressions though, so that part is type-safe. Actually this seems to work right.

Not sure if there is a way to encode kinds like (Type -> Type) -> Type (e.g. for monads), maybe by using a more restricted type than Function to encode the higher kinds.

@gcanti

This comment has been minimized.

Show comment
Hide comment
@gcanti

gcanti Nov 23, 2017

@astampoulis this is @hallettj's encoding I'm currently using in fp-ts

type Either<L, R> = { type: 'Left', value: L } | { type: 'Right', value: R }

type EitherF = <L, R>(x: [L, R]) => Either<L, R>
type ArrayF = <A>(x: [A]) => Array<A>

type ArrOfStrings = $Call<ArrayF, [string]>
type EitherOfStringNumber = $Call<EitherF, [string, number]>

;([1]: ArrOfStrings) // number. This type is incompatible with string
;({ type: 'Right', value: 'foo' }: EitherOfStringNumber) // string. This type is incompatible with number

gcanti commented Nov 23, 2017

@astampoulis this is @hallettj's encoding I'm currently using in fp-ts

type Either<L, R> = { type: 'Left', value: L } | { type: 'Right', value: R }

type EitherF = <L, R>(x: [L, R]) => Either<L, R>
type ArrayF = <A>(x: [A]) => Array<A>

type ArrOfStrings = $Call<ArrayF, [string]>
type EitherOfStringNumber = $Call<EitherF, [string, number]>

;([1]: ArrOfStrings) // number. This type is incompatible with string
;({ type: 'Right', value: 'foo' }: EitherOfStringNumber) // string. This type is incompatible with number
@PinkaminaDianePie

This comment has been minimized.

Show comment
Hide comment
@PinkaminaDianePie

PinkaminaDianePie Aug 30, 2018

Any updates here? It's so hard to use Flow for functional programming without this. :(

PinkaminaDianePie commented Aug 30, 2018

Any updates here? It's so hard to use Flow for functional programming without this. :(

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment