Generic, higher order functions

Question

I'm trying to add Flow type information to a small library of mine.

The library defines some functions that are generic over Object, Array, Set, Map and other types.

Here a small piece example to give an idea:

function set( obj, key, value ) {
  if( isMap(obj) )      { obj.set(key, value); }
  else if( isSet(obj) ) { obj.add(value);      }
  else                  { obj[key] = value;    }
}
function instantiateSameType( obj ) {
  if( isArray(obj) )    { return [];        }
  else if( isMap(obj) ) { return new Map(); }
  else if( isSet(obj) ) { return new Set(); }
  else                  { return {};        }
}
function forEach( obj, fn ) {
  if( obj.forEach ) obj.forEach(    ( value, key )=>fn(value, key, obj) );
  else Object.entries(obj).forEach( ([key, value])=>fn(value, key, obj) );
}
function map( obj, fn ) {
  const result = instantiateSameType( obj );
  forEach(obj, (value, key)=>{
    set( result, key, fn(value, key, this) );
  });
  return result;
}

How can I define types for map?

I'd want to avoid giving a specialized version for each of the 4 types I listed in the example, as map is generic over them. I feel the need to define higher-order interfaces, and implement them for existing types, but can't find much about any of this...

Any hints or ideas?

Answer 1

Update 2017-11-28: fp-ts is the successor to flow-static-land. fp-ts is a newer library by the same author. It supports both Flow and Typescript.

There is a library, flow-static-land, that does something quite similar to what you are attempting. You could probably learn some interesting things by looking at that code and reading the accompanying blog posts by @gcanti. I'll expand on the strategy in flow-static-land; but keep in mind that you can implement your iteration functions without higher-kinded types if you are OK with a closed set of iterable types.

As @ftor mentions, if you want polymorphic functions that can work on an open set of collection types then you want higher-kinded types (HKTs). Higher-kinded types are types that take type parameters, but with one or more of those parameters left unspecified. For example arrays in Flow take a type parameter to specify the type of elements in the array (Array<V>), and the same goes for maps (Map<K, V>). Sometimes you want to be able to refer to a parameterized type without specifying all of its type parameters. For example map should be able to operate on all arrays or maps regardless of their type parameters:

function map<K, A, B, M: Array<_> | Map<K, _>>(M<A>, fn: A => B): M<B>

In this case M is a variable representing a higher-kinded type. We can pass M around as a first-class type, and fill in its type parameter with different types at different times. Flow does not natively support HKTs, so the syntax above does not work. But it is possible to fake HKTs with some type alias indirection, which is what flow-static-land does. There are details in the blog post, Higher kinded types with Flow.

To get a fully-polymorphic version of map, flow-static-land emulates Haskell type classes (which rely on HKTs). map is the defining feature of a type class called Functor; flow-static-land has this definition for Functor (from Functor.js):

export interface Functor<F> {
  map<A, B>(f: (a: A) => B, fa: HKT<F, A>): HKT<F, B>
}

The HKT type is flow-static-land's workaround for implementing higher-kinded types. The actual higher-kinded type is F, which you can think of as standing in for Array or Map or any type that could implement map. Expressions like HKT<F, A> can be thought of as F<A> where the higher-kinded type F has been applied to the type parameter A. (I'm doing some hand waving here - F is actually a type-level tag. But the simplified view works to some extent.)

You can create an implementation of Functor for any type. But there is a catch: you need to define your type in terms of HKT so that it can be used as a higher-kinded type. In flow-static-land in the module Arr.js we see this higher-kinded version of the array type:

class IsArr {}  // type-level tag, not used at runtime
export type ArrV<A> = Array<A>;  // used internally
export type Arr<A> = HKT<IsArr, A>;  // the HKT-compatible array type

If you do not want to use Arr<A> in place of Array<A> everywhere in your code then you need to convert using inj: (a: Array<A>) => Arr<A> and prj: (fa: Arr<A>) => Array<A>. inj and prj are type-level transformers - at runtime both of those functions just return their input, so they are likely to be inlined by the JIT. There is no runtime difference between Arr<A> and Array<A>.

A Functor implementation for Arr looks like this:

const arrFunctor: Functor<IsArr> = {
  function map<A, B>(f: (a: A) => B, fa: Arr<A>): Arr<B> {
    const plainArray = prj(f)
    const mapped = plainArray.map(f)
    return inj(mapped)
  }
}

In fact the entire Arr.js module is an Arr implementation for Functor, Foldable, Traversable, and other useful type classes. Using that implementation with polymorphic code looks like this:

import * as Arr from 'flow-static-land/lib/Arr'
import { type Foldable } from 'flow-static-land/lib/Foldable'
import { type Functor } from 'flow-static-land/lib/Functor'
import { type HKT } from 'flow-static-land/lib/HKT'

type Order = { items: string[], total: number }

// this code is polymorphic in that it is agnostic of the collection kind
// that is given
function computeTotal<F> (
  f: Foldable<F> & Functor<F>,
  orders: HKT<F, Order>
): number {
  const totals = f.map(order => order.total, orders)
  return f.reduce((sum, total) => sum + total, 0, totals)
}

// calling the code with an `Arr<Order>` collection
const orders = Arr.inj([{ items: ['foo', 'bar'], total: 23.6 }])

const t = computeTotal(Arr, orders)

computeTotal needs to apply map and reduce to its input. Instead of constraining the input to a given collection type, computeTotal uses its first argument to constrain its input to types that implement both Foldable and Functor: f: Foldable<F> & Functor<F>. At the type-level the argument f acts as a "witness" to prove that the given collection type implements both map and reduce. At runtime f provides references to the specific implementations of map and reduce to be used. At the entry point to the polymorphic code (where computeTotal is called with a statically-known collection type) the Foldable & Functor implementation is given as the argument Arr. Because Javascript is not designed for type classes the choice of Arr must be given explicitly; but Flow will at least throw an error if you try to use an implementation that is incompatible with the collection type that is used.

To round this out here is an example of a polymorphic function, allItems, that accepts a collection, and returns a collection of the same kind. allItems is agnostic of the specific type of collection that it operates on:

import { type Monad } from 'flow-static-land/lib/Monad'
import { type Monoid, concatAll } from 'flow-static-land/lib/Monoid'
import { type Pointed } from 'flow-static-land/lib/Pointed'

// accepts any collection type that implements `Monad` & `Monoid`, returns
// a collection of the same kind but containing `string` values instead of
// `Order` values
function allItems<F> (f: Monad<F> & Monoid<*>, orders: HKT<F, Order>): HKT<F, string> {
  return f.chain(order => fromArray(f, order.items), orders)
}

function fromArray<F, A> (f: Pointed<F> & Monoid<*>, xs: A[]): HKT<F, A> {
  return concatAll(f, xs.map(f.of))
}

// called with an `Arr<Order>` collection
const is = allItems(Arr, orders)

chain is flow-static-land's version of flatMap. For every element in a collection, chain runs a callback that must produce a collection of the same kind (but it could hold a different value type). That produces effectively a collection of collections. chain then flattens that to a single level for you. So chain is basically a combination of map and flatten.

I included fromArray because the callback given to chain must return the same kind of collection that allItems accepts and returns - returning an Array from the chain callback will not work. I used a Pointed constraint in fromArray to get the of function, which puts a single value into a collection of the appropriate kind. Pointed does not appear in the constraints of allItems because allItems has a Monad constraint, and every Monad implementation is also an implementation of Pointed, Chain, Functor, and some others.

I am personally a fan of flow-static-land. The functional style and use of HKTs result in code with better type safety than one could get with object-oriented style duck typing. But there are drawbacks. Error messages from Flow can become very verbose when using type unions like Foldable<F> & Functor<F>. And the code style requires extra training - it will seem super weird to programmers who are not well acquainted with Haskell.

Answer 2

I wanted to follow up with another answer that matches up with the question that you actually asked. Flow can do just what you want. But it does get a bit painful implementing functions that operate on all four of those collection types because in the case of Map the type for keys is fully generic, but for Array the key type must be number, and due to the way objects are implemented in Javascript the key type for Object is always effectively string. (Set does not have keys, but that does not matter too much because you do not need to use keys to set values in a Set.) The safest way to work around the Array and Object special cases would be to provide an overloaded type signature for every function. But it turns out to be quite difficult to tell Flow that key might be the fully-generic type K or string or number depending on the type of obj. The most practical option is to make each function fully generic in the key type. But you have to remember that these functions will fail if you try to use arrays or plain objects with the wrong key type, and you will not get a type error in those cases.

Let's start with a type for the set of collection types that you are working with:

type MyIterable<K, V> = Map<K, V> | Set<V> | Array<V> | Pojo<V>
type Pojo<V> = { [key: string]: V } // plain object

The collection types must all be listed at this point. If you want to work with an open set of collection types instead then see my other answer. And note that my other answer avoids the type-safety holes in the solution here.

There is a handy trick with Flow: you can put the keyword %checks in the type signature of a function that returns a boolean, and Flow will be able to use invocations of that function at type-checking time for type refinements. But the body of the function must use constructions that Flow knows how to use for type refinements because Flow does not actually run the function at type-checking time. For example:

function isMap ( obj: any ): boolean %checks {
  return obj instanceof Map
}

function isSet ( obj: any ): boolean %checks {
  return obj instanceof Set
}

function isArray ( obj: any ): boolean %checks {
  return obj instanceof Array
}

I mentioned you would need a couple of type casts. One instance is in set: Flow knows that when assigning to an array index, the index variable should be a number, and it also knows that K might not be number. The same goes for assigning to plain object properties, since the Pojo type alias specifies string keys. So in the code branch for those cases you need to type-cast key to any, which effectively disables type checking for that use of key.

function set<K, V>( obj: MyIterable<K, V>, key: K, value: V ) {
  if( isMap(obj) )      { obj.set(key, value);    }
  else if( isSet(obj) ) { obj.add(value);         }
  else                  { obj[(key:any)] = value; }
}

Your instantiateSameType function just needs a type signature. An important point to keep in mind is that you use instantiateSameType to construct the result of map, and the type of values in the collection can change between the input and output when using map. So it is important to use two different type variables for the value type in the input and output of instantiateSameType as well. You might also allow instantiateSameType to change the key type; but that is not required to make map work correctly.

function instantiateSameType<K, A, B>( obj: MyIterable<K, A> ): MyIterable<K, B> {
  if( isArray(obj) )    { return [];        }
  else if( isMap(obj) ) { return new Map(); }
  else if( isSet(obj) ) { return new Set(); }
  else                  { return {};        }
}

That means that the output of instantiateSameType can hold any of values. It might be the same type as values in the input collection, or it might not.

In your implementation of forEach you check for the presence of obj.forEach as a type refinement. This is confusing to Flow because one of the types that make up MyIterable is a plain Javascript object, which might hold any string key. Flow cannot assume that obj.forEach will be falsy. So you need to use a different check. Re-using the isArray, etc. predicates works well:

function forEach<K, V, M: MyIterable<K, V>>( obj: M, fn: (value: V, key: K, obj: M) => any ) {
  if( isArray(obj) || isMap(obj) || isSet(obj) ) {
    obj.forEach((value, key) => fn(value, (key:any), obj));
  } else {
    for (const key of Object.keys(obj)) {
      fn(obj[key], (key:any), obj)
    }
  }
}

There are two more issues to point out: Flow's library definition for Object.entries looks like this (from core.js):

declare class Object {
    /* ... */
    static entries(object: any): Array<[string, mixed]>;
    /* ... */
}

Flow assumes that the type of values returned by Object.entries will be mixed, but that type should be V. The fix for this is to get values via object property access in a loop.

The type of the key argument to the given callback should be K, but Flow knows that in the array case that type will actually be number, and in the plain object case it will be string. A couple more type casts are necessary to fix those cases.

Finally, map:

function map<K, A, B, M: MyIterable<K, A>>(
  obj: M, fn: (value: A, key: K, obj: M) => B
): MyIterable<K, B> {
  const result = instantiateSameType( obj );
  forEach(obj, (value, key)=>{
    set( result, key, fn(value, key, this) );
  });
  return result;
}

Some things that I want to point out here: the input collection has a type variable A while the output collection has the variable B. This is because map might change the type of values. And I set up a type variable M for the type of the input collection; that is to inform Flow that the type of the callback argument obj is the same as the type of the input collection. That allows you to use functions in your callback that are particular to the specific collection type that you provided when invoking map.