Installation

Via npm:

# npm
npm install ts-expression

You can also use your favorite package manager:

# deno
deno add jsr:@lambda/ts-expression

# pnpm
pnpm add ts-expression

# bun
bun add ts-expression

# yarn
yarn add ts-expression

Examples

Representing 2D Points

import { car, cdr, cons } from "ts-expression";

type Point = typeof makePoint;

const makePoint = (x: number, y: number) => cons(x, y);
const getX = (point: Point) => car(point);
const getY = (point: Point) => cdr(point);

const getSymmetricalPoint = (point: Point) => {
  const x = getX(point);
  const y = getY(point);
  return makePoint(-x, -y);
};

const calculateDistance = (point1: Point, point2: Point) => {
  const [x1, y1] = [getX(point1), getY(point1)];
  const [x2, y2] = [getX(point2), getY(point2)];
  return Math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2);
};

const point1 = makePoint(3, 4);
const point2 = makePoint(0, 0);

getX(point1); // 3
getY(point2); // 0
getSymmetricalPoint(makePoint(1, 5)); // makePoint(-1, -5)
calculateDistance(makePoint(-2, -3), makePoint(-4, 4)); // ≈ 7.28

Building a Binary Tree

import { cons, car, cdr } from "ts-expression";

const leaf = <T>(value: T) => cons(value, cons(null, null));

const node = <N, L, R>(value: N, left: L, right: R) => {
  return cons(value, cons(left, right));
};

const tree = node(
  "root",
  node("left", leaf("left-left"), leaf("left-right")),
  node("right", leaf("right-left"), leaf("right-right")),
);

car(tree); // "root"
car(car(cdr(tree))); // "left"

File System path representation

import { cons, car, cdr } from "ts-expression";

const node = <A, B>(a: A, b: B) => cons(a, b);

const fs_tree = node(
  "dir:root",
  node(
    node("dir:usr", node("dir:bin", node("dir:etc", "file:readme.txt"))),
    node("dir:opt", node("dir:vol", node("dir:tmp", "file:script.sh"))),
  ),
);

const cdaar = car(car(cdr(fs_tree)));
const cdadar = car(cdr(car(cdr(fs_tree))));
const cdadddr = cdr(cdr(cdr(car(cdr(fs_tree)))));
const cddar = car(cdr(cdr(fs_tree)));

Mnemonic

The general rule for c[a/d][a/d][a/d][a/d]r functions:

• read from right to left (just like function composition)
• a stands for car (access the first element)
• d stands for cdr (drop the first element)

Basic Patterns

| Function | Equivalent Expression | Meaning | | ----------- | --------------------- | ----------------------------------- | | (car X) | (first X) | First element | | (cdr X) | (rest X) | Everything except the first element | | (cadr X) | (car (cdr X)) | Second element | | (cddr X) | (cdr (cdr X)) | Drops first two elements | | (caddr X) | (car (cdr (cdr X))) | Third element | | (cdddr X) | (cdr (cdr (cdr X))) | Drops first three elements |

Origin

This library provides a TypeScript implementation of symbolic expressions (S-expressions), which are a fundamental data structure in Lisp programming languages. S-expressions originated in the 1950s with John McCarthy's work on Lisp and have since become an elegant foundation for functional programming.

The core of S-expressions is the cons cell - a simple pair that holds two values. This primitive structure can be used to build complex data structures like lists, trees, and graphs. The operations to access the parts of a cons cell are traditionally called:

• car (Contents of Address Register) - retrieves the first/left element
• cdr (Contents of Decrement Register) - retrieves the second/right element

These peculiar names are historical artifacts from the IBM 704 computer on which Lisp was first implemented.

License

Made by a human being. Not LLM.

Copyright © 2024 Roman Hnatiuk

Licensed under MIT.