ronami / Meta Typing

📚 Meta-Typing

Functions and algorithms implemented purely with TypeScript's type system

Introduction

TypeScript's type system lets us catch bugs and errors in our code as we write it, instead of later on when the code runs. But... that's the obvious way to use the type system... 😜

This project attempts to push TypeScript's type system to its limits by actually implementing various functions and algorithms, purely on top of the type system.

Every implementation includes comments describing in detail what's going on. Some functions and algorithms use creative (and sometimes not officially supported) solutions to overcome some limitations of the type system.

☝ Please note that this project is meant to be used for fun and learning purposes and not for practical use.

Try running the code

Start by installing dependencies:

$ yarn

Open a file of any function or algorithm and hover over the types to see the results of "running" that function with some input (try hovering the resulting type).

You can also run tests (written with tsd) with:

$ yarn test

Functions and algorithms:

• Math:

  • Basic arithmetic - add one and decrease by one.
  • Add - adds two numbers.
  • Subtract - subtracts two numbers.
  • Multiply - multiplies two numbers.
  • Divide - divides two numbers.
  • Greater than or equal - checks if a value is greater than or equal to another value.
  • Less than or equal - checks if a value is less than or equal to another value.
  • Max - computes the maximum value of an array.
  • Min - computes the minimum value of an array.
  • Sum - computes the sum of the values in array.
  • Remainder - return the remainder (%) when one number is divided by a second number.

• Lists

  • Head - gets the first element of an array.
  • Tail - gets all but the first element of an array.
  • Reverse - Reverses an array so that the first element becomes the last, the second element becomes the second to last, and so on.
  • Size - gets the size of an array.
  • Concat - creates a new array by concatenating two arrays together.
  • Drop - creates a slice of an array with n elements dropped from the beginning.
  • Take - creates a slice of an array with n elements taken from the beginning.
  • Uniq - creates a duplicate-free version of an array.
  • Includes - checks if a value is an array.
  • IndexOf - gets the index at which the first occurrence of a value is found in an array.
  • Difference - creates an array of values from the first array that are not included in the other given arrays.
  • Intersection - creates an array of unique values that are included in all given arrays.
  • Slice - creates a slice of an array from start up to, but not including, end.
  • Flatten - flattens an array a single level deep.
  • Pull - removes all given values from an array.
  • Chunk - creates an array of elements split into groups the length of size.
  • Zip - creates an array of grouped elements, the first of which contains the first elements of the given arrays, the second of which contains the second elements of the given arrays, and so on.
  • Range - creates an array of numbers progressing from start up to, but not including, end.

• Sorting

  • Quick-sort - an efficient sorting algorithm.
  • Merge-sort - another efficient sorting algorithm.
  • Insertion-sort - a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

• Utility

  • IsEqual - compares between two values to determine if they are equivalent.

• Puzzles

  • N-Queens - the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.
  • Maze-solving - find the shortest path to solve a maze with obstacles.
  • Binary trees - a tree data structure in which each node has at most two children.
  • Square Matrix Rotation - you are given an N×N 2D matrix (representing an image). Rotate the matrix by 90 degrees (clockwise and counter-clockwise).
  • Towers of Hanoi - a mathematical game or puzzle that consists of three rods and a number of disks of different sizes.

Additional links

• Utility TypeScript types
• Advanced TypeScript types
• Typing the Technical Interview in TypeScript
• TypeScripts Type System is Turing Complete
• Emulating a 4-Bit Virtual Machine in TypeScript's type system
• Algorithms and data structures implemented in JavaScript
• How to master advanced TypeScript patterns