Skip to content
This repository has been archived by the owner on Aug 19, 2024. It is now read-only.

hnatiukr/pair-constructor

Repository files navigation

Warning

This library has been deprecated, so it will no longer get updates. Use ts-expression instead to stay up-to-date!

Pair Constructor

Tree-like data abstraction. TypeScript supported.

npm version npm version GNU GPL 3.0 License

import { cons, car, cdr } from 'pair-constructor';

const makePoint = (a, b) => cons(a, b);
const getX = (point) => car(point);
const getY = (point) => cdr(point);

const getSymmetricalPoint = (point) => {
  const x = getX(point);
  const y = getY(point);

  return makePoint(-x, -y);
};

const calculateDistance = (point1, point2) => {
  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
distance(point1, point2); // 5
getSymmetricalPoint(makePoint(1, 5)); // makePoint(-1, -5)
calculateDistance(makePoint(-2, -3), makePoint(-4, 4)); // ≈ 7.28

About

Symbolix expressions (S-expressions, sexp, sexpr) created with cons are immutable. This fits well with functional programming practices, where immutability is preferred. Using these constructs encourages practices that can lead to more predictable and bug-resistant code.

These operations allow for a minimalistic approach to handling complex data structures. They enable building lists and other composite data structures in a straightforward, efficient manner, which can be particularly useful in various algorithmic and data manipulation tasks.

By integrating these concepts into JavaScript/TypeScript, developers can leverage powerful functional programming techniques and gain deeper insights into the nature of data and computation.

Compound data: pairs

S-expression  /  CAR and CDR

Installation

Via npm

npm install pair-constructor

Via yarn

yarn add pair-constructor

Via pnpm

pnpm add pair-constructor

Via bun

bun add pair-constructor

Documentation

cons

Constructs a cons sexp from two values, car and cdr.

This function creates a symbolic expression that allows access to its car (first/left element) and cdr (second/right element) using specific messages. The resulting s-expression is an immutable structure where car and cdr can be accessed via the messages CAR and CDR, respectively.

Parameters

  • car CAR The first/left element of the s-expression.
  • cdr CDR The second/right element of the s-expression.

Examples

// Creating a sexp with a number and a string
const sexp = cons(5, 'hello');

// Accessing the first element using `CAR`
const five = sexp(CAR); // 5

// Accessing the second element using `CDR`
const hello = sexp(CDR); // 'hello'
  • Throws Error Throws an error if an unknown message is provided to the cons s-expression.

Returns Cons<CAR, CDR> A cons s-expression, which is a function that returns the car or cdr based on the provided message.

car

Retrieves the first element of a cons s-expression (known as car).

This function returns the left element of a s-expression created by the cons function. It ensures that the provided argument is a valid cons s-expression before attempting to access the element.

Parameters

  • cons Cons<CAR, CDR> The cons s-expression from which to retrieve the first element.

Examples

// Example usage
const sexp = cons(5, 'hello');

// Retrieves the first element of the s-expression
const five = car(sexp); // 5
  • Throws ReferenceError Throws an error if the provided argument is not a valid cons s-expression.

Returns CAR The first element (car) of the cons s-expression.

cdr

Retrieves the second element of a cons cons (known as cdr).

This function returns the right element of a cons created by the cons function. It ensures that the provided argument is a valid cons cons before attempting to access the element.

Parameters

  • cons Cons<CAR, CDR> The cons cons from which to retrieve the second element.

Examples

// Example usage
const sexp = cons(5, 'hello');

// Retrieves the second element of the sexp
const hello = cdr(sexp); // 'hello'
  • Throws ReferenceError Throws an error if the provided argument is not a valid cons cons.

Returns CDR The second element (cdr) of the cons cons.

toString

Converts a cons s-expression into its string representation, handling nested cons s-expression recursively.

This function generates a string representation of a cons s-expression by retrieving its car and cdr elements, converting them to strings using JSON.stringify, and formatting them in a tuple-like format. If either car or cdr is a nested cons s-expression, the function will recursively convert those elements to strings as well.

Parameters

  • cons Cons<CAR, CDR> The cons s-expression to be converted to a string.

Examples

// Example usage
const sexp = cons(cons(1, 2), cons('hello', 'world'));

// Convert the nested s-expression to a string
const str = toString(sexp); // "((1, 2), ("hello", "world"))"
  • Throws ReferenceError Throws an error if the provided argument is not a valid cons s-expression.

Returns string A string representation of the cons s-expression, including nested s-expressions, in the format (head, tail).

isCons

Checks if the provided argument is a cons symbolic expression.

This function determines if the given value is a cons s-expression by checking if it is a function and has a specific init property set to true. This property is used as a marker to identify cons s-expression, which are functions with the init property indicating their construction.

Parameters

  • maybeCons any The value to be checked. It can be of any type.

Examples

// Example of a valid cons s-expression
const sexp = cons(5, 'hello');

// Checking if it's a cons s-expression
const isValid = isCons(sexp); // true

// Example of an invalid cons s-expression
const notSexp = { car: 5, cdr: 'hello' };

// Checking if it's a cons s-expression
const isInvalid = isCons(notSexp); // false

Returns boolean true if the argument is a cons symbolic expression; otherwise, false.

assertCons

Asserts that the provided argument is a valid cons s-expression and throws a ReferenceError if it is not.

This function checks whether the given argument is a valid cons s-expression using the isCons function. If the argument is not a valid s-expression, an error is thrown with a detailed message that includes the serialized form of the invalid argument.

Parameters

  • maybeCons any The value to be checked, which can be of any type.

Examples

// Example of a valid cons s-expression
const sexp = cons(5, 'hello');

// Asserting the cons s-expression, no error is thrown
assertCons(sexp);

// Example of an invalid cons s-expression
const notSexp = { car: 5, cdr: 'hello' };

// Asserting the non-s-expression, an error is thrown
assertCons(notSexp); // Throws ReferenceError: Argument must be a symbolic expression, but it was '{"car":5,"cdr":"hello"}'
  • Throws ReferenceError Throws an error if the provided argument is not a valid cons s-expression.

Returns void

Examples of building abstraction levels based on pairs

The correct way to build a data structure is to follow the principle of one level of abstraction. This means that when working in one subject area on a certain slice, one should operate with objects of this slice only, avoiding objects that do not belong to it.

Abstraction Levels

1-st level: lower abstraction (Pairs)

const pair = cons('first', 'second');

car(pair); // => "first"
cdr(pair); // => "second"
isPair(pair); // true
toString(pair); // => "(first, second)"

2-nd level: higher abstraction (Coordinates of a Point)

const makePoint = (a, b) => cons(a, b);
const getX = (point) => car(point);
const getY = (point) => cdr(point);

const getQuadrant = (point) => {
  const x = getX(point);
  const y = getY(point);

  switch (true) {
    case x > 0 && y > 0:
      return 1;
    case x < 0 && y > 0:
      return 2;
    case x < 0 && y < 0:
      return 3;
    case x > 0 && y < 0:
      return 4;
    default:
      return null;
  }
};

const getSymmetricalPoint = (point) => {
  const x = getX(point);
  const y = getY(point);

  return makePoint(-x, -y);
};

const calculateDistance = (point1, point2) => {
  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
getQuadrant(point1); // 1
distance(point1, point2); // 5
getSymmetricalPoint(makePoint(1, 5)); // makePoint(-1, -5)
calculateDistance(makePoint(-2, -3), makePoint(-4, 4)); // ≈ 7.28

3-rd level: highest abstraction (Line Segments and an Objects)

const makeSegment = (point1, point2) => cons(point1, point2);

const startSegment = (segment) => car(segment);

const endSegment = (segment) => cdr(segment);

const segmentToString = (segment) => {
  const startToString = pointToString(startSegment(segment));
  const endToString = pointToString(endSegment(segment));

  return `[${startToString}, ${endToString}]`;
};

const midpointSegment = (point) => {
  const start = startSegment(point);
  const end = endSegment(point);

  const [x1, y1] = [getX(start), getY(start)];
  const [x2, y2] = [getX(end), getY(end)];

  const middleX = (x1 + x2) / 2;
  const middleY = (y1 + y2) / 2;

  return makePoint(middleX, middleY);
};

// ***

const segment = makeSegment(makePoint(1, 2), makePoint(-4, -2));
const point1 = startSegment(segment);
const point2 = endSegment(segment);

segmentToString(segment); // [(1, 2), (-4, -2)]
pointToString(point1); // (1, 2)
pointToString(point2); // (-4, -2)
pointToString(startSegment(segment)) === pointToString(makePoint(1, 2)); // true
pointToString(midpointSegment(segment)); // (-1.5, 0)

Other examples

Rational numbers as pairs of values: numerator and denominator

const make = (numer, denom) => cons(numer, denom);

const numer = (rat) => car(rat);

const denom = (rat) => cdr(rat);

const toString = (rat) => `${numer(rat)} / ${denom(rat)}`;

const isEqual = (rat1, rat2) => numer(rat1) * denom(rat2) === denom(rat1) * numer(rat2);

const add = (rat1, rat2) => {
  const [a, b] = [numer(rat1), denom(rat1)];
  const [c, d] = [numer(rat2), denom(rat2)];

  return make(a * d + b * c, b * d); // (a * d + b * c) / (b * d)
};

const sub = (rat1, rat2) => {
  const [a, b] = [numer(rat1), denom(rat1)];
  const [c, d] = [numer(rat2), denom(rat2)];

  return make(a * d - b * c, b * d); // (a * d - b * c) / (b * d)
};

const mul = (rat1, rat2) => {
  const [a, b] = [numer(rat1), denom(rat1)];
  const [c, d] = [numer(rat2), denom(rat2)];

  return make(a * c, b * d); // (a * c) / (b * d)
};

const div = (rat1, rat2) => {
  const [a, b] = [numer(rat1), denom(rat1)];
  const [c, d] = [numer(rat2), denom(rat2)];

  return make(a * d, b * c); // (a * d) / (b * c)
};

// ***

const rat1 = make(2, 3);
const rat2 = make(4, 6);
const rat3 = make(7, 2);

toString(rat2); // '4 / 6'
isEqual(rat1, rat2); // true

add(rat1, rat3); // 25/6
sub(rat3, rat1); // 17/6
mul(rat1, rat3); // 14/6
div(rat1, rat3); // 4/21

Inspirations

I’ve embraced the "Structure and Interpretation of Computer Programs" (SICP) and LISP's abstractions to deeply understand and appreciate functional programming and data manipulation. These foundational concepts highlight the power of simple, immutable data structures in building complex systems, emphasizing clarity and expressive power in code.