JS Journey into outer space

This article was written as part of a knowledge sharing program I created for front-end developers. It builds up to creating reusable abstractions by studying async transducers.

Day 5

It's time to add more operators. We already have map, but what if the mapping function returns another "container" value, like an array or observable?

🦉 In RxJS some operators like switchMap, concatMap, or mergeMap will expect a "project" function that returns an observable (or promise or array), but what happens then? First map is applied with the project function and after that the result is "flattened". In other words: when the returned (inner) observables emit, the mapped (outer) observable emits those values instead. Since RxJs streams have a specific async behaviour the flattening process takes concurrency into account: mergeMap will flatten inner observables whenever they complete, regardless of the order, but concatMap will preserve the order of the outer observable. Finally, switchMap will flatten only the most recent inner observable, discarding all previous results from the project function.

How did mergeMap work again? We use it often when the result returned from the project function and we're interested in all the values.

const pause = (ms: number) => new Promise((resolve) => {
  setTimeout(() => {
    resolve(ms);
  }, ms);
});
const result = of(1, 2, 3).pipe(mergeMap((n: number) => pause(n * 100)));
result.subscribe(console.log); // 100, 200, 300

🦉 Flattening of arrays was introduced in ES2019 and follows the exact same pattern of many existing implementations and languages. Methods flatten and flatMap were added to the Array prototype.

And then this happened

Let's first look at the array example. To flatMap we need to first provide a function to map that returns an array and then flatten the result, so... wait, what? It already did? Uh oh.

const monoidArray = array.getMonoid<number>();
const result = transduce(
  [1, 2, 3],
  compose(map((x) => [x, x * 2]))(monoidArray.concat),
  iterator,
  monoidArray.empty
);
console.log(result); // [1, 2, 2, 4, 3, 6]

The skilled reader already discovered that concat has a different type than is actually used. For arrays the JavaScript implementation will accept both arrays (or array-like values) and other values: in case the value isn't an array it will be appended. To be honest, Monoid was mainly introduced to explain typeclasses, so we'll need to iron this detail out now.

🦉 To add a single item at the end of a list in Haskell (where typeclasses originated) one actually has to use the monoidal concat operation and provide a new list with a single item as the second argument. The size of lists isn't dynamic like that of JavaScript arrays, so the performance for adding a single item is similar to concatenating arrays. In general, merging iterables by iterating seems to be preferred approach in functional programming.

Higher and kind

As you see we need a transduce function that is truly polymorphic, that is, it has to contain knowledge about which type is passed in and use the correct instances of Monoid, Subscribable, Failable and Completable when that type is encountered. However, since we already know which implementations these type classes need we can compose them in several ways. All that is needed is to infer the type of transducable at runtime and decide which implementations to use. Ideally, this selection process is configurable, something like

(a, previousTransduce) => Array.isArray(a) ? transduceArray(a) : previousTransduce(a);

However, before we do let's consider the true type of transduce.

"A higher-kinded type is a type that abstracts over some type that, in turn, abstracts over another type."

When reading a sentence like that most people's brains usually stop processing half way. Those people need something concrete to see the abstract, if at all. Let's look at the type of Functor in fp-ts.

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

No bullet point with owl here. We should be used to these alien names by now. It's just a type class that defines the map behaviour (i.e. "mappable" types). However, the type signature of map contains an even more alien thing: the three-letter acronym of HKT, AKA higher-kinded type. And what's with the URI in this interface? See the following snippets adapted from Intro to fp-ts, part 1: Higher-Kinded Types . See the article for a more in-depth explanation.

interface Functor<F> {
  readonly map: <A, B>(f: (a: A) => B) => (as: F<A>) => F<B>; // Type 'F' is not generic. ts(2315)
}

The subtype of F, which is the mappable type, can't be expressed in this way in TypeScript. The type arguments need to be defunctionalized, which means that F needs to be replaced by some unique identifier and wrapped with the Kind type constructor, which expresses any type constructor in a generic way. The Kind constructor, however, has a fixed arity (that is the number of type arguments the type constructor can take). Addtionally, the relation between the unique type identifier and the polymorphic type will be encoded in a dictionary:

interface URItoKind<A> {
  'Array': Array<A>;
} // a dictionary for 1-arity types: Array, Set, Tree, Promise, Maybe, Task...
interface URItoKind2<A, B> {
  'Map': Map<A, B>;
} // a dictionary for 2-arity types: Map, Either, Bifunctor...

type URIS = keyof URItoKind<any>; // sum type of names of all 1-arity types
type URIS2 = keyof URItoKind2<any, any>; // sum type of names of all 2-arity types
// and so on, as you desire

type Kind<URI extends URIS, A> = URItoKind<A>[URI];
type Kind2<URI extends URIS2, E, A> = URItoKind2<E, A>[URI];

// and so on

Now the interface we want can be expressed (for a fixed arity).

export interface Functor1<F extends URIS> {
  readonly URI: F
  readonly map: <A, B>(fa: Kind<F, A>, f: (a: A) => B) => Kind<F, B>
}

export interface Functor2<F extends URIS2> {
  readonly URI: F
  readonly map: <E, A, B>(fa: Kind2<F, E, A>, f: (a: A) => B) => Kind2<F, E, B>
}

Finally we need one more level of abstraction to express all available type arities.

interface HKT<URI, A> {
  readonly _URI: URI
  readonly _A: A
}

This is the most abstract things can get in JavaScript and perhaps the value is debatable. However, abstraction is like a mountain that can be climbed time and again to gain a clear and calming view when stuck in the daily toil of software development. Living on that altitude is not for everyone, but look at all those tiny houses below in the valley...

Search This Blog

Craft & Artfulness