single-platter

single-platter

Generic and safe boilerplate removal for operations on recursive data types. Based off of the Uniplate Haskell library.

Install

npm install --save single-platter

Motivation

Operations on recursive data types generally require defining one case per variant. For example, consider a recursive data type Expr for defining arithmetic expressions:

type Add = {
    tag: "Add";
    left: Expr;
    right: Expr;
};

type Sub = {
    tag: "Sub";
    left: Expr;
    right: Expr;
};

type Mul = {
    tag: "Mul";
    left: Expr;
    right: Expr;
};

type Div = {
    tag: "Div";
    left: Expr;
    right: Expr;
};

type Val = {
    tag: "Val";
    value: number;
};

type Neg = {
    tag: "Neg";
    inner: Expr;
};

export type Expr = Add | Sub | Mul | Div | Val | Neg;

Say we have an Expr and we want to simplify it by removing all subtraction operations, replacing them with the addition of a negation operation. So this:

{
    tag: "Sub",
    left: x,
    right: y
}

should turn into this:

{
    tag: "Add",
    left: x,
    right: {
        tag: "Neg",
        inner: y
    }
}

To do this normally, we need to define a recursive function which operates over every node in the tree. Here's the naive implementation:

function removeSubExplicit(expr: WithoutLet.Expr): WithoutLet.Expr {
    if (expr.tag === "Add")
        return {
            tag: "Add",
            left: removeSubExplicit(expr.left),
            right: removeSubExplicit(expr.right),
        };
    if (expr.tag === "Sub")
        return {
            tag: "Add",
            left: removeSubExplicit(expr.left),
            right: {
                tag: "Neg",
                inner: removeSubExplicit(expr.right),
            },
        };
    if (expr.tag === "Mul")
        return {
            tag: "Mul",
            left: removeSubExplicit(expr.left),
            right: removeSubExplicit(expr.right),
        };
    if (expr.tag === "Div")
        return {
            tag: "Div",
            left: removeSubExplicit(expr.left),
            right: removeSubExplicit(expr.right),
        };
    if (expr.tag === "Val") return expr;

    return {
        tag: "Neg",
        inner: removeSubExplicit(expr.inner),
    };
}

Here we've defined six cases, only one of which is "interesting". The more variants in our recursive data structure, the worse this uninteresting boilerplate becomes.

Here is how the same operation is defined with single-platter:

function removeSub(expr: Expr): Expr {
    return plate.transform(expr, (expr) =>
        expr.tag === "Sub"
            ? {
                  tag: "Add",
                  id: expr.id,
                  left: expr.left,
                  right: {
                      tag: "Neg",
                      id: "",
                      inner: expr.right,
                  },
              }
            : expr,
    );
}

This function definition is less than half as many lines. Even better, this line reduction makes the logic easier to understand by highlighting the relevant transformation and omitting irrelevant distractions. Even better, this definition is stack-safe, as none of the operations in this library use recursion internally. The naive implementation will crash on sufficiently-large inputs.

single-platter provides seven highly-flexible generic operations which can be used to make a broad range of transformations simpler and safer.

Usage

This library supports both ESM and CommonJS imports.

The sole export of this library is the Plate class. Plate must be instantiated with functions for getting all of the children of a recursive node, and for creating a new node from an existing node and a new set of children. For example, using our Expr language above:

import { Plate } from "single-platter";

function getChildren(expr: Expr): Array<Expr> {
    if (expr.tag === "Add") return [expr.left, expr.right];
    if (expr.tag === "Sub") return [expr.left, expr.right];
    if (expr.tag === "Mul") return [expr.left, expr.right];
    if (expr.tag === "Div") return [expr.left, expr.right];
    if (expr.tag === "Val") return [];
    return [expr.inner];
}

function fromChildren(expr: Expr, children: Array<Expr>): Expr {
    if (expr.tag === "Add")
        return {
            tag: "Add",
            left: children[0]!,
            right: children[1]!,
        };
    if (expr.tag === "Sub")
        return {
            tag: "Sub",
            left: children[0]!,
            right: children[1]!,
        };
    if (expr.tag === "Mul")
        return {
            tag: "Mul",
            left: children[0]!,
            right: children[1]!,
        };
    if (expr.tag === "Div")
        return {
            tag: "Div",
            left: children[0]!,
            right: children[1]!,
        };
    if (expr.tag === "Val")
        return {
            tag: "Val",
            value: expr.value,
        };
    return {
        tag: "Neg",
        inner: children[0]!,
    };
}

const plate = new Plate(getChildren, fromChildren);

The fromChildren implementation uses non-null assertions when accessing the children array. Users must ensure that, for every variant in their data type, getChildren(node) returns an array of the same length that fromChildren uses to create that variant. This is not enforced (and not practically enforceable) by the type system.

API

Documentation for Plate's methods lives separately:

• children(node): Return all of a node's children
• universe(tree): Return all of the nodes in a tree
• transform(tree, fn): Rewrite a tree from the bottom up
• descend(node, fn): Traverse over a single layer of a tree
• rewrite(tree, fn): Efficiently rewrite a tree into a normal form
• para(tree, fn): Perform a paramorphism over a tree
• contexts(tree): Retrieve a complete list of a tree's one-hole contexts

Limitations

Monadic Uniplate operations have been omitted

The Haskell Uniplate library provides monadic versions of descend, rewrite, and transform. TypeScript's type system doesn't make representing these operations ergonomic. If you need an effectful transformation it is recommended that you pass impure functions to transformation methods.

For example, if you wish to annotate every node in a tree with a unique ID, you should use transform, passing in a function which uses an impure getFreshID operation.

Mutually recursive data types are not supported

This library only supports recursion over a single data type. As a point of comparison, many programming languages are defined via mutually recursive types, such as Statement and Expression types which each reference each other. The original Haskell Uniplate library handles this via the Biplate typeclass. Biplate is more involved than single-type Uniplate and is not implemented in this library.

I would be open to PRs to change this!

Contributing

Please see CONTRIBUTING.md.

Contributions and interactions made by or with the assistance of agentic or generative AI are not welcome and will result in an immediate ban from the project.

Some desired features are listed in WISHLIST.md.

License

MIT

Citations

This project is heavily based on the contents of a research paper:

Neil Mitchell and Colin Runciman. 2007. Uniform boilerplate and list processing. In Proceedings of the ACM SIGPLAN workshop on Haskell workshop (Haskell '07). Association for Computing Machinery, New York, NY, USA, 49–60. https://doi.org/10.1145/1291201.1291208