programming

Type-level Collatz Sequence

The Collatz conjecture is an unsolved problem in mathematics. It states that for any positive integer n, the sequence of numbers generated by the following algorithm will eventually reach 1. These are also called the hailstone numbers. function collatz(n: number): number { return n % 2 === 0 ? n / 2 : 3 * n + 1; } The sequence generated by a given $n$ is the sequence of numbers n, collatz(n), collatz(collatz(n)), collatz(collatz(collatz(n))), and so on.

Typesafe Function Composition

Do ya wanna know how to type function composition in Typescript? Read on! 1. Background 1.1. Type-theoretic Pseudocode 2. Typescript 2.1. IsComposablePair 2.1.1. Type-based Pattern Matching using infer 2.1.2. IsComposablePair 2.2. Every 2.3. Pair 3. Component Synthesis 4. Function Integration 5. Future Work: Constructive Approach 1. Background Function composition is an operation that takes two functions, $f$ and $g$, and produces a new function $h$ such that $h(x) = g(f(x))$.

Towards a well-typed plugin architecture

declare abstract class EnginePlugin<I = unknown, D = unknown> { createInterface?(ø: Record<string, unknown>): I getDependencies?(): D } type Defined<T> = T extends undefined ? never : T type ExtractPlugins<T> = T extends Engine<infer PX> ? PX : never type UnionToIntersection<U> = ( U extends unknown ? (k: U) => void : never ) extends (k: infer I) => void ? I : never type MergeInterfaces< E extends Engine, K extends keyof EnginePlugin, > = UnionToIntersection<ReturnType<Defined<ExtractPlugins<E>[number][K]>>> type Assume<T, U> = T extends U ?

A non-recursive type-level inclusion operator

type E1<X> = <T>() => T extends X ? 0 : 1 type E2<X> = <T>() => T extends X ? 0 : 1 type IsEqual<X, Y> = E1<X> extends E2<Y> ? true : false /** * Whether or not T includes U as an element. */ type Includes<T extends readonly unknown[], U> = true extends { [key in keyof T]: IsEqual<T[key], U> }[number] ? true : false A non-recursive type-level Includes operator in Typescript Introduction Includes is a type-level operator that determines whether a given type T includes a given type U as an element.

Point-free Programming via HKTs

In Typescript, point-free programming has been traditionally limited due to the difficulty the type system has representing the abstracted types associated with point-free (also called ’tacit’) programming. 1. What is Tacit Programming? 2. Type-Level Programming 2.1. The Hard (Naive) Way 2.2. Tacit Logic via HKTs 3. Addendum: Library 3.1. Basic HKT Abstractions 3.2. HKT Composition 3.3. Narrow Type Inference 3.4. Value-level Apply 3.5. Auto-applyable HKTs 3.