This content originally appeared on Level Up Coding - Medium and was authored by Gregory Pabian
The type system of TypeScript makes it possible to use recursive and nested types. Under certain scenarios, software developers can flatten types with nested values to gain simplicity; for instance, when flattening a two‐dimensional array to a one-dimensional one. This article outlines the relevant parts of the category theory connected to flattening and showcases exemplary implementations.
The Category Theory
The category theory proposes a construct of a monad, a value container that acts as proxy for manipulation of applicable values. In functional programming, monads serve as fundamental structures used for holding values within computational pipelines. The most popular ones (according to my experiences so far) include the Option, Either, Task, Array, Set, and Map monads.
Traditionally, monads require two functions to exist:
- a monadic constructor (called of or wrap), which accepts a single parameter and produces a monad containing the passed value,
- a monadic combinator (called bind, chain or flatMap), with a monad as the first parameter, and another monadic constructor (with a non-trivial logic) as the second parameter; the combinator passes the monadic value into the aforementioned constructor and returns the newly-created monad.
In TypeScript, one could consider the ReadonlyArray<T> as a monad, since it contains a collection of values and exposes the following methods:
- Array.prototype.of, Array.prototype.from and Array.prototype.constructor, which, under certain circumstances, can each serve as a monadic constructor,
- Array.prototype.flatMap, which acts as a monadic combinator.
The existence of the monadic combinator indirectly implies that a monad of a monad (a nested monad) behaves just like a simple monad. In the monadic world, developers should treat an array of an array, until specified otherwise, as a one-dimensional array. Most professionals know of “reducing the nested structures to their simplified counterparts” as flattening and this article goes into depth to explain how to write flattening code efficiently.
Monads in TypeScript
The type system of TypeScript allows developers to create monadic types with ease. Such a type must hold a value (or values) and preferably, a type-discriminating property to distinguish it from other monads. I have provided a basic implementation of the Option<T> monad down below:
I have chosen type as the discriminator property for the Option type; it can accept either someOptionSymbol or noneOptionSymbol as values. I would prefer a symbol not as a property value, but a property itself (for its preferential treatment when iterating over object properties), but as of TypeScript 4.2, discriminated unions still do not work with symbol-keyed properties. Usage of symbols mitigates possible structure injections coming from code not managed by the Option mechanics.
Chaining
Software developers might use monadic combinators in a pipeline (chaining) to bypass issues with nested monads before they even occur. Instead of permitting the creation of nested monads, the combinators, if applied in the correct order, should restrict nesting to the first level of complexity (the simple monads). In a way, one could think of such a function as a composition of mapping and flattening, hence some people name it flatMap.
The monadic combinator, called chainOption, uses the partial application design pattern. The non-trivial monadic constructor, ctor acts as the first partially-applied parameter, with the option monad acting as the second one. In the end, the implementation of the functionality boils down to 3 active lines of code, as shown down below:
I have provided an example on how to use chainOption in practice. The multiplyByTen function, a partially-applied chainOption instance, provides a mapping operation within the number monad (I would advise the reader to check the presented signature). The code snippet, visible underneath, shows how applying multiplyByTen two times produces a simple number monad:
Nested Flattening
One could transform a monad of a monad (or, in other words, a second-level nested monad) into a simple monad by just extracting its value. The very implementation of the basic flattening depends heavily on the monad type in question. I created an example for the Option<T> monad, available down below:
One can apply the basic flattening in a pipeline as many times as needed to achieve the desired level of nesting. The example underneath presents how one can flatten a nestedOption (a third-level nested monad) into a simple monad. This solution works well with low-level nested monads, as adding a few layers of flattening should not exhaust developers.
Explicit Flattening
The prototype of the Array object contains an intriguing method called flat. Its user might define the depth of flattening to apply to the array in question, reducing the number of eventual flattening calls to a single invocation. I have read the TypeScript definitions for that method quite carefully and this inspired me to think of a way to port them into the monadic world.
I would like to start with creating a type that describes a nested monad of any level. An exemplary implementation of the NestedOption<T, L extends number> (L like level), available underneath, exploits the law that for L > 1 a NestedOption<T, L> equals Option<NestedOption<T, L-1>>. I would advise the reader to run a thought experiment on how the TypeScript compiler might resolve NestedOption<string, 5> into the final type.
With the NestedOption type defined, I can finally introduce the flattenNestedOption, visible down below. Unfortunately, because of the complexity of types and limitations of TypeScript, I needed to use @ts-ignore to hide type discrepancies. If the reader finds a way around this problem, please write a comment in the comment section.
Applying the flattenNestedOption function boils down to figuring out the level of nesting and calling the function with the nested monad, as presented in the example beneath. Having a function that figures out the level of nesting in runtime would serve as the apex improvement. I will leave it to the reader to think of a proper implementation of such a challenge.
Summary
The category theory has introduced the concept of monads to allow developers to abstract away some operations on values. Recursive and nested types, under certain circumstances, might adhere to the definition of a monad, and thus the developers can leverage monadic laws when working with such types. Flattening, managed by the aforementioned laws, serves as a prime example of applying concepts coming from mathematics into software development.
Flattening in TypeScript was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Gregory Pabian
Gregory Pabian | Sciencx (2021-04-13T13:21:20+00:00) Flattening in TypeScript. Retrieved from https://www.scien.cx/2021/04/13/flattening-in-typescript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.