Algebraic structures in FP

Table of contents

• what do we mean by algebraic structure
• Laws
• Reasoning for laws
• Relationship between structures
• Groups are everywhere

what do we mean by algebraic structure

An algebraic structure is a mathematical "object"(system, setup, tuple) consisting of a set of elements equipped with one or more operations that satisfy certain properties, axioms or laws. These structures provide a formal framework for studying and understanding the relationships and properties of mathematical objects.

In general, an algebraic structure is defined by:

1. Underlying Set: A non-empty set 𝑆 whose elements are the building blocks of the structure.

2. Operations: One or more operations defined on the set 𝑆S. These operations can include addition, multiplication, composition, etc., depending on the specific structure.

3. Properties, Axioms or laws: A set of properties or axioms that the operations must satisfy to define the structure. These properties may include closure, associativity, commutativity, identity elements, and inverses, among others. (please don't jump at the high school memories)

here's a short list of algebraic structures from which we'll pick the ones that are actually used in functional programming.

1. Magma
2. Semigroup
3. Monoid
4. Group
5. Abelian group
6. Ring
7. Field

Sounds abstract and a bit foreign? of course it does but see algebraic structures all the time in computer programming and your real life.

Laws

We're going to take the a group-like structure to demonstrate the laws (that you should already know) as is the structure that encompass the most laws of the list

// Define a type for the elements of the group
type GroupElement = number;

// Define the group interface
interface Group {
  // Binary operation
  operation(x: GroupElement, y: GroupElement): GroupElement;

  // Identity element
  identity: GroupElement;

  // Inverse operation
  inverse(x: GroupElement): GroupElement;
}

// Define a function to check if an object satisfies the Group interface
function isGroup(object: any): object is Group {
  return (
    typeof object.operation === 'function' &&
    typeof object.identity !== 'undefined' &&
    typeof object.inverse === 'function'
  );
}

// Define a concrete implementation of a group: integers under addition
const integerAdditionGroup: Group = {
  operation: (x, y) => x + y,
  identity: 0,
  inverse: x => -x,
};

// Test the properties of the group
function testGroupProperties(group: Group): boolean {
  const { operation, identity, inverse } = group;
  // Closure property
  const closure = (a: GroupElement, b: GroupElement) => isGroup(operation(a, b));
  // Associativity property
  const associativity = (a: GroupElement, b: GroupElement, c: GroupElement) =>
    operation(a, operation(b, c)) === operation(operation(a, b), c);
  // Identity property
  const identityElement = (a: GroupElement) => operation(a, identity) === a && operation(identity, a) === a;
  // Inverse property
  const inverseElement = (a: GroupElement) => operation(a, inverse(a)) === identity && operation(inverse(a), a) === identity;
  // Test properties for a range of elements
  for (let i = -100; i <= 100; i++) {
    if (!closure(i, i) || !associativity(i, i, i) || !identityElement(i) || !inverseElement(i)) {
      return false;
    }
  }
  return true;
}

// Test if integers under addition form a group
console.log(testGroupProperties(integerAdditionGroup)); // Output: true

Reasoning for laws

But first a detour through similes between math laws and society's legal laws to make the point more clear.

Air travel industry:
Failure to adhere to safety regulations and standards can result in accidents and incidents with devastating consequences. for example, if an airline neglects maintenance procedures or ignores safety protocols, it increases the risk of mechanical failures, mid-air emergencies, and crashes.

Food industry:
Failure to comply with food safety regulations can lead to contamination of food products with pathogens, toxins, or foreign objects. Contaminated food can cause foodborne illnesses, outbreaks of diseases such as salmonella or E. coli, and potentially fatal consequences for consumers.

laws provide predictability, confidence, order, stability likewise in the world of software development they give us the same:

• Correctness and Reliability: Laws define expected behavior and properties of functional constructs. By adhering to these laws, developers can write code that behaves predictably and reliably. For example, the associativity law for monoids ensures that combining values in different orders yields the same result, which helps maintain correctness in programs that use monoidal operations.

• Equational Reasoning: Laws enable equational reasoning, which allows developers to reason about code by substituting expressions that are known to be equivalent. This simplifies reasoning and facilitates understanding, debugging, and refactoring of functional code. For instance, knowing the laws of monads allows developers to reason about sequences of computations in a clear and systematic way.

• Abstraction and Composition: Laws provide a foundation for abstraction and composition in functional programming. By defining common properties and behaviors, laws enable the creation of composable and reusable components. Developers can leverage these abstractions confidently, knowing that they adhere to well-defined laws and can be combined safely.

• Verification and Testing: Laws serve as a basis for verifying the correctness of functional code through testing. Developers can write property-based tests that validate whether code adheres to specified laws. If code violates these laws, it indicates potential bugs or incorrect implementations, enabling early detection and resolution of issues.

• Interoperability and Interchangeability: Laws promote interoperability and interchangeability of functional components. Functional constructs that satisfy the same laws can be used interchangeably, regardless of their specific implementations. This enables developers to mix and match components from different libraries or languages seamlessly, fostering code reuse and modularity.

Relationship between structures

Construction from Smaller Structures: Some algebraic structures can be constructed from simpler ones. For instance, a group is just a monoid that adds an inverse element for each element in the original set and likewise a monoid is just a semigroup that adds one element which combined with any other elements returns the latter. We've already saw that the set of integers under addition forms a Group if we take the negative numbers and start from the 0 onwards we have a monoid, but if we then take the 0 which is the identity element we end only with positive integers that together with the combine function forms a semigroup.

Containment Hierarchies: Certain algebraic structures contain or are substructures of others.
This is very interesting given that the majority of the primitives in your programming language of choice falls implicitly under one of these structures and we can make them conform to the structures interfaces very easily and get all the benefits of the laws automatically and for free. let's see an example, JSON:

We can convert a JSON document very easily into a monoid (which is one of the most useful and used structures) by converting all of its fields into monoids and delegating the sub-operations. Isn't this just cool?

(A quick-n-dirty naive version would be like this)

type JsonValue = string | number | boolean | null | JsonObject | JsonArray;
type JsonObject = { [key: string]: JsonValue };
type JsonArray = JsonValue[];

// Define a monoid interface for JSON values
interface JsonMonoid {
  empty: JsonValue;
  concat: (x: JsonValue, y: JsonValue) => JsonValue;
}

// Define monoids for each JSON data type
const stringMonoid: JsonMonoid = {
  empty: "",
  concat: (x, y) => `${x}${y}`,
};

const numberMonoid: JsonMonoid = {
  empty: 0,
  concat: (x, y) => x + y,
};

const booleanMonoid: JsonMonoid = {
  empty: false,
  concat: (x, y) => x || y,
};

const nullMonoid: JsonMonoid = {
  empty: null,
  concat: (_, y) => y,
};

const objectMonoid: JsonMonoid = {
  empty: {},
  concat: (x, y) => {
    const result: JsonObject = { ...x };

    for (const key in y) {
      if (y.hasOwnProperty(key)) {
        result[key] = key in result ? objectMonoid.concat(result[key], y[key]) : y[key];
      }
    }

    return result;
  },
};

const arrayMonoid: JsonMonoid = {
  empty: [],
  concat: (x, y) => [...x, ...y],
};

// Define a function to recursively apply the monoid operation based on the JSON value type
const mergeJsonValues = (x: JsonValue, y: JsonValue): JsonValue => {
  if (typeof x !== typeof y) {
    throw new Error("Incompatible types");
  }

  if (typeof x === "object" && x !== null && Array.isArray(x) === Array.isArray(y)) {
    // Recursively merge arrays and objects
    return Array.isArray(x) ? arrayMonoid.concat(x, y as JsonArray) : objectMonoid.concat(x as JsonObject, y as JsonObject);
  } else {
    // Delegate to the appropriate monoid based on the data type
    switch (typeof x) {
      case "string":
        return stringMonoid.concat(x as string, y as string);
      case "number":
        return numberMonoid.concat(x as number, y as number);
      case "boolean":
        return booleanMonoid.concat(x as boolean, y as boolean);
      case "object":
        return nullMonoid.concat(x as null, y as null);
    }
  }
};

// Test the monoid
const obj1: JsonObject = { a: { b: 1 }, c: 2 };
const obj2: JsonObject = { a: { d: 3 }, e: 4 };

const result = objectMonoid.concat(obj1, obj2);
console.log(result); // Output: { a: { b: 1, d: 3 }, c: 2, e: 4 }

From the last example you now see that objets and arrays form a monoid too, you just didn't know they were

Groups are everywhere

from the clock on the wall:

class ClockGroup {
    private readonly size: number;
    private readonly hours: number[];

    constructor(size: number) {
        this.size = size;
        this.hours = Array.from({ length: size }, (_, i) => i);
    }

    add(clock1: number, clock2: number): number {
        return (clock1 + clock2) % this.size;
    }

    subtract(clock1: number, clock2: number): number {
        return (clock1 - clock2 + this.size) % this.size;
    }

    identity(): number {
        return 0;
    }

    inverse(clock: number): number {
        return (this.size - clock) % this.size;
    }

    print(): void {
        console.log("Clock Group:");
        console.log("Elements:", this.hours);
        console.log("Size:", this.size);
    }
}

// Example usage
const clockGroup = new ClockGroup(12);
clockGroup.print();

console.log("Addition (5 + 7):", clockGroup.add(5, 7)); // Output: 0 (12-hour clock wraps around)
console.log("Subtraction (7 - 5):", clockGroup.subtract(7, 5)); // Output: 2
console.log("Identity element:", clockGroup.identity()); // Output: 0
console.log("Inverse of 8:", clockGroup.inverse(8)); // Output: 4

to rubik's cube:

// Define a type for the colors of the Rubik's Cube faces
type CubeColor = 'red' | 'blue' | 'green' | 'orange' | 'white' | 'yellow';

// Define a type for the Rubik's Cube face
interface CubeFace {
    color: CubeColor;
}

// Define a type for the Rubik's Cube
type RubiksCube = CubeFace[][][];

// Define a Group interface
interface Group<T> {
    operation(a: T, b: T): T;
    identity: T;
    inverse(a: T): T;
}

// Define the Rubik's Cube group interface that extends the Group interface
interface RubiksCubeGroup extends Group<CubeRotationCommand> {
    // No additional methods needed as rotation commands directly represent cube rotations
}

// Define a rotation command interface
interface CubeRotationCommand {
    axis: 'x' | 'y' | 'z'; // Axis of rotation
    layer: number; // Layer of the cube to rotate
    direction: 'clockwise' | 'counter-clockwise'; // Direction of rotation
}

// Implementation of RubiksCubeGroup
class MyRubiksCubeGroup implements RubiksCubeGroup {
    operation(command1: CubeRotationCommand, command2: CubeRotationCommand): CubeRotationCommand {
        // Combine two rotation commands
        // In practice, this could involve composing the sequences of rotations
        return command1; // Placeholder implementation
    }

    get identity(): CubeRotationCommand {
        // Identity element: no rotation
        return { axis: 'x', layer: 0, direction: 'clockwise' }; // Placeholder implementation
    }

    inverse(command: CubeRotationCommand): CubeRotationCommand {
        // Inverse of a rotation command
        // In practice, this could involve reversing the rotation
        return command; // Placeholder implementation
    }
}

// Example usage
const rubiksCubeGroup: RubiksCubeGroup = new MyRubiksCubeGroup();
console.log("Identity:", rubiksCubeGroup.identity);
console.log("Inverse of 'U':", rubiksCubeGroup.inverse('U'));
console.log("Operation of 'U' and 'R':", rubiksCubeGroup.operation('U', 'R'));

overall everywhere you find some kind of symmetry there's good chance you'll find a type of algebraic structure.

FIN