Rendering React components with recursion schemes
Nested data structures
Some time ago at work we were implementing platform for file exchange. Think GDrive but backed by client internal storage service. So our main challenge was to manipulate and present file system hierarchy. I bet that for every functional programmer file hierarchy would scream to use some kind of recursive data structure, however most JavaScript developers tend to store their data as maps (disguised as plain js objects). This probably comes from the fear of recursion, which to me it is natural way of traversing recursive data structures.
Thankfully over quarter of a century ago some smart people realized that you could abstract out act of traversal through recurrent data structures. Using their findings bunch of libraries were implemented. I believe that the most famous and complete is Haskell implementation, however in this post I am going to use it’s JavaScript counterpart. That allows us to define transformations for only single level of nested data. Next we’ll plug this function to one of so called recursion schemes, to get all the data processed.
Types at play
Before we dive any further let us define data types that we’ll be dealing with. I’ll be using flow typing throughout this article1. We have single file:
type File = {
extension: string,
id: FileId,
name: string,
owner: User,
preview: Url,
thumbnail: Url,
type: 'File',
uploaded: string,
url: Url
}
There are some standard properties that everyone would expect like: name, id and extension. Instead let’s turn our attention to the type
property which should always be set to ‘File’ string. This will let us recognize that the object at hand is indeed a File. Other than this type
props, File
is pretty straightforward.
Another entity in the file system hierarchy is much more interesting:
Beside the obvious, we have:
type
property that is always set to ‘Directory’. This will allow us to distinguish betweenFile
and aDirectory
.children
which is an parameterized Array.
In contrast to the File
type, although it may not be obvious, Directory
is our recurrent element.
One final basic data type is sum type of file and directory (since file system value can be of type File
OR Directory
).
We’ll be passing FileSystemV
values everywhere, but to make decision based on it’s type we will check type
property value to make decision based on the actual data type2.
You are probably wondering why we need parameter R
. Well right now the best explanation I can give is: because recursion schemes requires that our data is presented that way. If you are curious why, you’ll have to dive into internals of how recursion schemes work.
There are just 2 more requirements to start using recursion schemes.
Functor instance
Another step that is required is to define Functor instance for our data type. In short Functors are data containers that can be mapped over3 (just like an array, which you are familiar with).
Problem with Functors is that Flow doesn’t support Higher Kinded Types. To work around that we need a little boilerplate.
export class IsFileSystem {}
export type FileSystemF<R> = HKT<IsFileSystem, R>
export function inj<A> (a: FileSystemV<A>): FileSystemF<A> {
return ((a: any): FileSystemF<A>)
}
export function prj<A> (a: FileSystemF<A>): FileSystemV<A> {
return ((a: any): FileSystemV<A>)
}
FileSystemF<R>
is our functor, prj
and inj
will help us transform values back and forth from internal representation to functor.
So all that is left is to implement map
function for FileSystemF.
function map<A, B> (f: A => B, a: FileSystemF<A>): FileSystemF<B> {
const node: FileSystemV<A> = prj(a)
let result
switch (node.type) {
case 'Directory':
result = {
...node,
children: node.children.map(f)
}
break
default:
case 'File':
result = { ...node }
break
}
return inj(result)
}
Basically we map over all children of a directory and just return files. If you wonder why we are not doing anything to files, take a look at the types we have! We have function f
which takes 1 parameter and that parameter is single content of a Directory
children array. There is nothing to be done to a File
.
Fixed point
You might have noticed that our FileSystem functor can only hold only one level file system hierarchy. How do we make it so we can hold hierarchy of arbitrary many levels?
We have to use fixed point operator. The static-land-recursion-schemes library defines one so we don’t have to. However if you are interested how it works under the hood take a look here or there.
FileSystem
type represent file system hierarchy of arbitrary nesting.
Utility functions
It is convenient to define simple helper functions that can create file and directory.
function file (f: File): FileSystem {
return new In(inj(f))
}
function directory (
id: FileId,
name: string,
children: Array<FileSystem>
): FileSystem {
return new In(inj({
id, name, children, type: 'Directory'
}))
}
This way we can create simple structure to test code.
const fs = directory('root', '', [
directory('home', 'home', [
directory('home0', 'john', [
file(files[0]),
file(files[1]),
directory('john_temp', 'tmp', [ file(files[2]) ])
]),
directory('home1', 'mary', [
file(files[3]),
directory('mary_temp', 'tmp', [ file(files[4]) ])
]),
directory('home2', 'al', [])
])
])
Where files
is just some array with dummy data.
Catamorphism
In this article I’ll use just 1 recursion scheme: catamorphism. Although it name may be little scary it may become easier when you realize that it comes from Greek κατα meaning “downwards” as in “catastrophe”. Which means that it collapses data structure into single value. So you can think about it sort of like generalized reduce.
Besides the input data, catamorphism requires function in the form: FileSystemF<a> => a
. Such function is called Algebra. It takes as an argument Functor containing value of type a
and produces single value of type a
. Intuitively cata traverses structure bottom up, and passes to the algebra result of previous steps. But enough of that, let’s jump to examples!
Pretty printing
Before anything else let’s implemented FileSystem pretty printer, just to see some output on the terminal. Pretty printer takes FileSystem
as an argument and return string
as a result. To traverse file system will gonna use cata
from static-land-recursion-schemes, which as first argument takes Functor instance. Because of static-land convention this is object with key map
, which is mapping function as defined before.
Second parameter is Algebra. To keep track of all the files as FileSystemF functor argument I have used Array of strings. If the current node is single File we return singleton array with the file name. In the case of Directory we prepend its name to all its contents.
To obtain final result we join the array with new line symbol.
const prettyPrint = (a: FileSystem): string => {
const alg = (a: FileSystemF<Array<string>>): Array<string> => {
const node = prj(a)
switch (node.type) {
case 'Directory':
return node.children.length === 0 ? [`${node.name}/[empty]`]
: node.children.reduce(
(a, b) => a.concat(
b.map(y => `${node.name}/${y}`)
),
[]
)
case 'File':
default:
return [`${node.name}`]
}
}
const msg = cata({ map }, alg, a)
return msg.join('\n')
}
Filtering
More interesting example is filter function for FileSystem. Filter takes 2 arguments: first is predicate function which takes single FileSystem element and returns a boolean which indicates whether this element should be kept in resulting FileSystem. Second argument to filter is FileSystem to be filtered.
function filterFS (p: FileSystemV<FileSystem> => boolean, fs: FileSystem): FileSystem {
function alg (entry: FileSystemF<FileSystem>): FileSystem {
const node = prj(entry)
if (node.type === 'Directory') {
return directory(
node.id,
node.name,
node.deletable,
node.children.filter(e => p(prj(out(e))))
)
}
return file(node)
}
return cata({ map }, alg, fs)
}
Our filter algebra basically applies predicate to each directory children using builtin array filtering method and simply passes along files. However usually this is not the filter function user wants. Most of the time we want to specify predicate on File
type and do not include empty directories. Such function can be defined in terms of filterFS
, like so:
function filterFiles (p: File => boolean, fs: FileSystem): FileSystem {
return filterFS(a => {
if (a.type === 'Directory') {
return a.children.length !== 0
}
return p(a)
}, fs)
}
React component
I saved the best for end :) The promise of recursion schemes is that we can write down easy single level transformation, plug it in to the scheme and get transformed data. So here we define 2 react components: File and Directory, to render their corresponding file system elements. By the way I am some of these react componenets.
export type Props = {
name: string,
owner: string,
policy: string,
uploaded: string
}
const File = ({ name, owner, type, uploaded }: Props) => (
<li role='treeitem'>
<div>
<div>
<span title={name}>{name}</span>
</div>
<div>{owner}</div>
<div>{uploaded}</div>
</div>
</li>
)
export type Props = {
children: React.Node,
name: string,
}
const Directory = ({ children, name }: Props) => (
<li role='treeitem'>
<div>
<Button type='icon' icon='chevronright'>
<span>Expand {name}</span>
</Button>
<Icon icon='folder' />
<span title={name}>{name}</span>
</div>
<ul role='group'>
{children}
</ul>
</li>
)
Having those to components defined we can easily create function that will render any FileSystem. All we have to do is to fold (reduce) our FileSystem
into React.Node
. To achieve this we’ll use catamorphism with very simple algebra. Do you know what type signature of Algebra is needed in this case? Its function alg (e: FileSystemF<React.Node>): React.Node
! Yes we will use the same functor as before, but hold values of React.Node
inside. Right now you should be understanding why recursion scheme requires us to define our data as functors. Algebra itself is very simple: just check whether current node is File
or Directory
and return appropriate component.
const fileTree = (fs: FileSystem): React.Node => {
/* fold to react component */
function alg (entry: FileSystemF<React.Node>): React.Node {
const node = prj(entry)
if (node.type === 'Directory') {
return (
<Directory name={node.name}>
{node.children}
</Directory>
)
}
return <File
name={node.name}
owner={node.owner.name}
type={node.format}
/>
}
return cata({ map }, alg, fs)
}
What is left is to just wrap fileTree
into some tags, and pass it some data. It can be filtered down (with previous catamorphism) data:)
export type Props = {
fs: FileSystem
}
const FileMgr = ({ fs }: Props) => (
<ul aria-labelledby='treeheading'
role='tree'
>
{ fileTree(fs) }
</ul>
)
Conclusion
I think I’ve presented interesting case for recursion schemes in JavaScript. Front end developers usually fear deeply nested structures. Thanks to some old and battle-tested methods we can traverse through those structures with ease. By abstracting out the traversal developer can focus on transforming data at hand.
Although in the next project I would select TypeScript over flow.↩
It is worth noting that using JavaScript classes and flow/TypeScript interfaces would allow for more elegant implementation of concepts presented here. However at our project we were using Redux and it recomends storing simple serializable objects in the store.↩
In addition map function should hold some properties, but let’s not bother with that in this article.↩