Type Guard Composition

Type guards are a powerful tool for type system design. They are used to express that a type is only valid if it satisfies a certain condition. For example, we can express that a type is only valid if it is a number or a string. 1. Union Type Guards 1.1. Naive Union Implementation 1.2. 2-adic Union Composition 1.3. N-adic Union Composition 1.3.1. GuardReturnType 1.3.2. Variadic Is-Union 1.3.3. References for this Section 2.

Programs of Length N: Collatz, Chaitin, and Church

There are a few interesting questions about the nature of programs, and specifically about sets of programs, as represented by lambda calculus expressions. 1. How many programs have N terms? 2. How fast does the set of programs of length N grow? 3. How many programs of length N converge? 4. What is the longest-running convergent program of length N? 5. How fast does BB(N) grow? 6. What percentage of programs converge?

Unchained Tuple Types

The asserts syntax introduced with TS 3.7 allows us to interleave mutative runtime code with type annotations to express type mutations in a powerful way. This allows us to do away with the chaining syntax as described in my earlier article, Chained Tuple Types, and express our Set mutations in a much more familiar iterative way: const set: Set = new Set(); set.insert(2); set.insert(4); set.insert(8); set.remove(4); const hasResult1 = set.has(8); // :: true const hasResult2 = set.

String Deduplication on the Type Level

The string deduplication problem is a canonical one within computer science, serving a similar purpose as fizz-buzz in terms of being an example of a simple problem that a reasonably knowledgable practitioner should be able to solve with minimal effort. The problem appears in a few variants, but briefly one such variant is to remove duplicate letters in a given string, such that the string then has only one instance of any given letter.

Chained Tuple Types

With Typescript 4.1, it’s now possible to use variadic tuple types to construct large types with what appears to be runtime code. The general idea is that we will utilize a chaining pattern, where each operation on the chain returns an expanded version of the chain’s type. To motivate the example, let us consider a Set class. Our Set is a chaining class, where you may insert, remove, and check for the existence of numbers.

Enforcing Function Map Constraints

Some “easy to state” problems in Typescript can require somewhat sophisticated type constructs. Let’s say you want to enforce that every function in a particular map takes in as its first parameter, either a number or a string: type PermissibleInput = number | string; const myFunctionMap = { foobar(x: number): void; barfoo(y: string): void; } If you do this in the naive way, as e.g. Record<string, (number | string) => any>, you will discover that this type actually encodes the requirements that every function must support both input types - which is a problem, as myFunctionMap is not actually composed of such functions.

Self Modifying Type Predicates in Typescript

Typescript’s type system is uniquely powerful among mainstream programming languages, approximating the expressive power of Haskell or Idris, while also remaining flexible enough for production applications. Type predicates are a useful tool in building a well-typed software framework. Essentially, they allow you to “simulate” dependent types, a powerful type feature present in Idris. Further explanation on type predicates can be found here. The premise of this article is a usage of type predicates I haven’t seen discussed online - most type predicates just modify one of their arguments, but you can actually form a predicate on this because it is an implicit argument.

Dijkstra's Shunting Yard in Typescript

The shunting yard algorithm converts infix expressions (i.e. 1+2) into reverse Polish notation, i.e. 1 2 +, which lends itself well to execution on a stack machine. An aside: I wanted to revisit this algorithm because it was one of the first I implemented in C during self-study five years ago. In a way, reimplementing it is a way of measuring my progress since then. The internal details aren’t too complicated - it’s based on the simple pseudo-code of the Wikipedia article describing the shunting yard algorithm.

Bay Area SSC Meetup

I’m in SF for the summer, and I was thus able to attend the Slate Star Codex meetup this year in Dolores Park. Met a lot of interesting people, and got to meet Scott. While I’m in the Bay Area I hope to get a little more involved in that scene. Picture is of the park, not the meetup specifically.

Pythagorean Triple Problem in Sub-linear Time

The Pythagorean triple problem is as follows. Given an input integer \(n\), return integers \(a\), \(b\), \(c\) such that the two following conditions hold: $$ a b c = n $$ $$ a^2 + b^2 = c^2 $$ I was interested in finding a solution to this problem that was both succint and had good asymptotic complexity. The solution I found runs in O(sqrt(n)) time by deconstructing the problem into the well-known 3SUM problem.