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 article¹. 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:

type Directory<R> = {
  children: Array<R>,
  id: FileId,
  name: string,
  type: 'Directory'
}

Beside the obvious, we have:

1. type property that is always set to ‘Directory’. This will allow us to distinguish between File and a Directory.
2. 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).

type FileSystemV<R> = File | Directory<R>

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 type².

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 over³ (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?

type FileSystem = FileSystemF<FileSystemF<FileSystemF< ...? >>>

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.

type FileSystem = Fix<IsFileSystem>

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.