Flow: position of polymorphic params should not affect behavior

[Gozala]

Edit: Turns out issue was something different from what I assumed first, feel free to skip over to https://github.com/facebook/flow/issues/954#issuecomment-149315797

export type Zip = <x,y,z> (f:(x:x, y:y) => z, xs:Array<x>, ys:Array<y>)
                => Array<z>

export const zip:Zip = (f, xs, ys) => {
  const zs = []
  const count = Math.min(xs.length, ys.length)
  let index = 0
  while (index < count) {
    zs[index] = f(xs[index], ys[index])
    index = index + 1
  }
  return zs
}

This produces following errors:

src/scratch.js:5
  5: export type Zip = <x,y,z> (f:(x:x, y:y) => z, xs:Array<x>, ys:Array<y>)
                            ^ z. This type is incompatible with
  8: export const zip:Zip = (f, xs, ys) => {
                            ^ some incompatible instantiation of z

src/scratch.js:13
 13:     zs[index] = f(xs[index], ys[index])
                       ^^^^^^^^^ x. This type is incompatible with
  8: export const zip:Zip = (f, xs, ys) => {
                            ^ some incompatible instantiation of x

src/scratch.js:13
 13:     zs[index] = f(xs[index], ys[index])
                                  ^^^^^^^^^ y. This type is incompatible with
  8: export const zip:Zip = (f, xs, ys) => {
                            ^ some incompatible instantiation of y


Found 3 errors

But if I inline all type declarations as follows, flow reports no errors:

export const zip = <x, y, z> (f:(x:x, y:y) => z, xs:Array<x>, ys:Array<y>):Array<z> => {
  const zs = []
  const count = Math.min(xs.length, ys.length)
  let index = 0
  while (index < count) {
    zs[index] = f(xs[index], ys[index])
    index = index + 1
  }
  return zs
}

[Gozala]

Also example without arrays seem to work as expected:

/* @flow */
export type $compineWith <x, y, z>
  = (f:(x:x, y:y) => z, x:x, y:y) => z

export const combineWith:$compineWith = (f, x, y) => f(x, y)

[Gozala]

Ok it seems that issue is with f function call inside a loop, where flow assumes that x & y could be mutated and there for invalidate invariants http://flowtype.org/docs/dynamic-type-tests.html#caveats

Although I still find it odd that behavior is different if type annotations are inlined, or maybe it's a bug that flow does not error in that case ?

Anyway I have update code to try to avoid invalidation:

/* @flow */

export type $zip = <x,y,z> (f:(x:x, y:y) => z, xs:Array<x>, ys:Array<y>)
                => Array<z>

export const zip:$zip = (f, xs, ys) => {
  const zs = []
  let index = 0
  while (index < xs.length && index < ys.length) {
    zs[index] = f(xs[index], ys[index])
    index = index + 1
  }
  return zs
}

But I still get unexpected errors back:

rc/scratch.js:3
  3: export type $zip = <x,y,z> (f:(x:x, y:y) => z, xs:Array<x>, ys:Array<y>)
                             ^ z. This type is incompatible with
  6: export const zip:$zip = (f, xs, ys) => {
                             ^ some incompatible instantiation of z

src/scratch.js:10
 10:     zs[index] = f(xs[index], ys[index])
                       ^^^^^^^^^ x. This type is incompatible with
  6: export const zip:$zip = (f, xs, ys) => {
                             ^ some incompatible instantiation of x

src/scratch.js:10
 10:     zs[index] = f(xs[index], ys[index])
                                  ^^^^^^^^^ y. This type is incompatible with
  6: export const zip:$zip = (f, xs, ys) => {
                             ^ some incompatible instantiation of y


Found 3 errors

BTW: I find these error messages very confusing, I wish they've also included links to those caveats or to lengthier explanations.

So in the above example I presumed that call to f could mutate array by changing it length although I would not expect it to change element types otherwise what's the point of saying it's Array<x> and Array<y> no ?

I also wish there was a way to relax flow about the mutations maybe something like ImmutableArray<x> ? Although maybe it should be something else but Immutable to imply no mutations with in this call frame not in general ?

[Gozala]

I have further modified my example to try to avoid the invalidation issue:

/* @flow */

export type $zip = <x,y,z> (f:(x:x, y:y) => z,
                            xs:Array<x>,
                            ys:Array<y>) => Array<z>

export const zip:$zip = (f, xs, ys) => {
  xs = xs.slice(0)
  ys = ys.slice(0)

  const zs = []
  let index = 0
  while (index < xs.length && index < ys.length) {
    const x = xs[index]
    const y = ys[index]
    const z = f(x, y)
    zs.push(z)
    index = index + 1
  }
  return zs
}

but I still get some errors:

  3: export type $zip = <x,y,z> (f:(x:x, y:y) => z,
                         ^ x. This type is incompatible with
  7: export const zip:$zip = (f, xs, ys) => {
                             ^ some incompatible instantiation of x

src/scratch.js:3
  3: export type $zip = <x,y,z> (f:(x:x, y:y) => z,
                           ^ y. This type is incompatible with
  7: export const zip:$zip = (f, xs, ys) => {
                             ^ some incompatible instantiation of y

src/scratch.js:3
  3: export type $zip = <x,y,z> (f:(x:x, y:y) => z,
                             ^ z. This type is incompatible with
  7: export const zip:$zip = (f, xs, ys) => {
                             ^ some incompatible instantiation of z


Found 3 errors

[Gozala]

Oddly enough if I move polymorphic parameters in front of the = everything works as expected:

/* @flow */

export type $zip <x,y,z> = (f:(x:x, y:y) => z,
                            xs:Array<x>,
                            ys:Array<y>) => Array<z>

export const zip:$zip = (f, xs, ys) => {
  xs = xs.slice(0)
  ys = ys.slice(0)

  const zs = []
  let index = 0
  while (index < xs.length && index < ys.length) {
    const x = xs[index]
    const y = ys[index]
    const z = f(x, y)
    zs.push(z)
    index = index + 1
  }
  return zs
}

[Gozala]

Looks like the actual issue was with where polymorphic parameter were listed (before or after) assignment in type alias. I do think that should not have an effect behavior on behavior, meaning that following two type aliases should be identical:

  type foo <x, y> = (x:x) => y
  type foo = <x, y> (x:x) => y

Alternatively one of them can be a syntax error, which would make it easier for user to fix it.

If there are subtle differences between those two declarations maybe that difference should be explained somewhere at length ?

P.S. Updating title to reflect the actual issue.

[samwgoldman]

So the premise of this issue isn't really true. It does change the behavior and it should change the behavior. These two definitions mean different things:

type A<T> = (x: T) => T;
type B = <T>(x: T) => T;

The simplest way to show how they are different is by considering possible inhabitants.

Let's start with B. In fact, there is exactly 1 inhabitant of B—the identity function. By parametricity, I can prove that for any f : B, f(x) === x.

Now A. Does the same proof hold? Well, no. For f: A<T>, T can be some concrete thing, like number. For f: A<number>, we can assign something like x => x + 1, or x + 2, or x + 3 and so on.

[mwalkerwells]

@samwgoldman Are there any plans to improve the documentation around this?

[mwalkerwells]

@samwgoldman One note on documentation: While I think Flow has poor documentation coverage on "advanced" topics, your answers and responsiveness on Github issues have been incredibly helpful to me.

[AlexanderShushunov]

@samwgoldman Documentation is very confusing.
It says that <T>(param: T) => T is right definition of generic function type.