Disjoint union type filtering is not respected when filtering arrays

[noahtallen]

Reproduced here.

We basically have an array of a disjoint union type. So we have multiple elements in the array, and we differentiate between them based on a type property. I use the array method filter to essentially only get an array of objects of one type. However, flow does not infer that the results will only be of the one type. How do I work around this?

[wchargin]

This is a known limitation. The problem is that the type of filter is
roughly

declare class Array<T> {
  filter(predicate: (T) => boolean): Array<T>;
}

so when you call testArray.filter, Flow only knows that you’re calling
a function of this type; it doesn’t know anything special about filter
itself. A function of this type might do any number of things: it could

• filter only elements matching the predicate (which filter does),
• or filter only elements not matching the predicate,
• or return the input unchanged,
• or return every odd-indexed element of the input in reverse order,
• etc.

That the type of the result array should be refined according to your
predicate depends on a contract of filter that is not expressed in
this type, and so Flow doesn’t know about it.

I don’t have a good workaround other than a cast through any. This
would be a nice place in which to use safe downcasting: you could write

const res: Object1[] = $Downcast(testArray.filter((x) => x.type === 'one'));

to express that you are guaranteeing to Flow that the type of the result
is actually more specific than Flow can infer. If this appeals to you,
feel free to post on the feature request thread at #6482.

(Also related: #6397.)

[noahtallen]

I do like the way that looks, thanks for the suggestion. Unfortunately, though $Downcast does sound enticing, I would rather flow support it automatically. For instance, as shown in the docs, flow can automatically infer which type you are using in many cases (such as if statements). What part of the engine stops it from being able to also check the predicate I pass to filter to see how I may be refining the types within the predicate? Though I do understand the example type you provided, instead of introducing another advanced feature to Flow to hack around this problem, would it be possible to rather improve the inference system?

[chisui]

flows refinement system can't infer the types of anything that is not in the current scope. For everything outside of the current scope flow has to rely on the exposed signature. The fact that filter is part of the standard library doesn't give it any special behavior for local type refinements.

The problem here is that the there is no way expressing that the predicate used in filter only holds for values of a given type. Since these predicates are plain functions there has to be some part of the function that is parameterized with the expected result type for filter to grab onto to. (a: A) => boolean simply doesn't have enough information.

This problem exists in every language that has map/filter functionality. There is a trick to get around this though. Since all we need is to have a way to grab onto the expected result type we have to find a function that takes a function that includes it. What about map?

interface Array<A> {
   ...
   map(f: (a:A) => B)): Array<B>;
   ...
}

The return type of the mapping function f is exactly what we need to encode the wanted return type. Inside this function we can check if the element is of the desired type and then return an array only containing that value or an empty array. We now have an Array<Array<B>> which we can flatten to get an Array<B> that only contains the desired values.

Try

As you can see inside the mapping function type refinements work out of the box even without explicit type annotations on the return type.

Unfortunately the flatten function isn't part of the standard library. On the other hand the much more powerful flatMap function is coming to javascript in the next release. It combines map with flatten into a single function. In the meantime you can get this functionality through libraries like ramda where this function is called chain

This trick also works for the java Stream API and in purely functional languages like Haskell (where this concept is called a Monad).

[noahtallen]

Thanks for the informative answer!

[wchargin]

would it be possible to rather improve the inference system?

It depends on what you mean by this.

It’s not currently possible to even write down the type that you’d
like filter to have. You need to declare that your callback takes in
arbitrary T but only returns true when the input is actually some
more specific type U. Something like…

declare class Array<T> {
  function filter<U>(p: PredicateReturningTrueOnlyFor<U>): Array<U>;
}

So, if you mean, “keeping the current grammar of types and values, is it
possible to improve Flow’s inference engine so that it can solve this
case automatically?” then I believe that the answer is “no”, because the
inference engine always spits out some type, and here there is no
type that correctly captures the strength of filter’s contract.

(Related: an explanation of why Array.prototype.find’s behavior with
respect to side-effects cannot be encoded with Flow’s current
grammar.)

But maybe you’re willing to permit expanding the grammar to give us more
powerful type constructors. In this case, it is possible, though it
comes at the cost of “introducing another advanced feature to Flow”. In
fact, this particular extension has been an undocumented feature in
Flow’s codebase for years, and there are test cases ensuring that it
works: the mechanism provides $Pred<n> (a predicate function taking
n arguments) and $Refine<T, P, k> (a type T that has been refined
as the kth argument to P). So you get code like this:

declare function my_filter<T, P: $Pred<1>>(v: Array<T>, cb: P): Array<$Refine<T,P,1>>;

declare var arr: Array<mixed>;
const barr = my_filter(arr, is_string);
(barr: Array<string>);

function is_string(x): %checks {
  return typeof x === "string";
}

I don’t know what the status of this code is, but it doesn’t look like
it’s seen much activity since 2016. It also pushes more complexity onto
the user: the user has to know about %checks functions, for one.

though $Downcast does sound enticing, I would rather flow support it
automatically

So would I! Sorry that this may not be a satisfying answer; it’s just
the state of affairs as I understand it.

[noahtallen]

That's really helpful! I definitely appreciate the in-depth explanations you guys have given about how Flow works. That other thread was also helping in understanding the limitations and possible improvements Flow could see.