Instantly share code, notes, and snippets.

Justin Meiners justinmeiners

Last active January 13, 2024 00:48

There's a simple recipe for arithmetically encoding recursive algebraic data types (in the functional programming sense) which is related to this.

What you might have seen is Goedel numbering where a finite sequence of natural numbers a_0, a_1, ..., a_n (where n isn't fixed but can vary per sequence) is mapped bijectively onto p_0^a_0 a_1^p_1 ... a_n^p_n where p_0, p_1, ... is an enumeration of the primes.

However, if you want to represent trees instead of sequences, you have a better, simpler option. The key is the existence of a bijective pairing function between N^2 and N, which you can write as <m, n> for m, n in N.

You have a lot of choices for how to construct the pairing function. But a curious fact is that there is essentially one polynomial pairing function and it's the one you saw in class when you learned that the rationals are countable: https://en.wikipedia.org/wiki/Fuet

Last active June 16, 2024 02:08
html->string (Super simple HTML templating for Lisp)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; Copyright (c) 2020 Mark Polyakov ;; Released under the WTFPL (Do What The Fuck You Want To Public License) (defvar *html-void-tags* '(:area :base :br :col :embed :hr :img :input :link :meta :param :source :track :wbr) "String designators for self-closing/void tags. https://html.spec.whatwg.org/multipage/syntax.html#void-elements") (defvar *html-escapes* '(#\> ">"
Last active March 23, 2024 16:28
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // x64 encoding enum Reg { RAX, RCX, RDX, RBX, RSP, RBP, RSI, RDI, R8, R9, R10, R11, R12, R13, R14, R15, }; enum XmmReg { XMM0, XMM1, XMM2, XMM3, XMM4, XMM5, XMM6, XMM7, XMM8, XMM9, XMM10, XMM11, XMM12, XMM13, XMM14, XMM15,
Last active May 17, 2020 04:35

The trick to designing transpose algorithms for both small and large problems is to recognize their simple recursive structure.

For a matrix A, let's denote its transpose by T(A) as a shorthand. First, suppose A is a 2x2 matrix:

[A00 A01]
A = [A10 A11]

Then we have:

Last active June 10, 2024 10:31
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 template _NODISCARD /* constexpr */ _Ty _Common_lerp(const _Ty _ArgA, const _Ty _ArgB, const _Ty _ArgT) noexcept { // on a line intersecting {(0.0, _ArgA), (1.0, _ArgB)}, return the Y value for X == _ArgT const int _Finite_mask = (int{isfinite(_ArgA)} << 2) | (int{isfinite(_ArgB)} << 1) | int{isfinite(_ArgT)}; if (_Finite_mask == 0b111) { // 99% case, put it first; this block comes from P0811R3 if ((_ArgA <= 0 && _ArgB >= 0) || (_ArgA >= 0 && _ArgB <= 0)) { // exact, monotonic, bounded, determinate, and (for _ArgA == _ArgB == 0) consistent: return _ArgT * _ArgB + (1 - _ArgT) * _ArgA;
Last active April 29, 2021 16:50
Extracting Pure Functions in Swift Without Polluting the Global Namespace

For testability purposes (and to make things easier to reason about), sometimes it's nice if methods in a class are pure functions, that is, they don't contain any explicit or implicit references to self, or really anything other than the arguments that are passed in.

In the painfully contrived example below, method is a method (because it references both a property and another method using self) and isEven is a pure function (because it doesn't).

class MyClass {
let number: Int

init(number: Int) {
Created January 30, 2020 03:50
Let's Destroy C

Let's Destroy C

I have a pet project I work on, every now and then. CNoEvil.

The concept is simple enough.

What if, for a moment, we forgot all the rules we know. That we ignore every good idea, and accept all the terrible ones. That nothing is off limits. Can we turn C into a new language? Can we do what Lisp and Forth let the over-eager programmer do, but in C?

Last active March 21, 2023 21:47
SQL implementation of Largest Triangle Three Bucket time series sampling algoritm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 create type point_t as (x float, y float); create type triangle_t as (p1 point_t, p2 point_t, p3 point_t, surface float); create function largest_triangle_accum (maxsurfacetriangle triangle_t, p1 point_t, p2 point_t, p3 point_t) returns triangle_t language SQL as \$\$ select case when maxsurfacetriangle is null or triangle_surface(p1,p2,p3) > maxsurfacetriangle.surface
Last active May 14, 2024 05:30
A random dungeon generator that fits on a business card
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #include // Robert Nystrom #include // @munificentbob #include // for Ginny #define r return // 2008-2019 #define l(a, b, c, d) for (i y=a;y\
Last active November 5, 2023 13:11

A quadratic space is a real vector space V with a quadratic form Q(x), e.g. V = R^n with Q as the squared length. The Clifford algebra Cl(V) of a quadratic space is the associative algebra that contains V and satisfies x^2 = Q(x) for all x in V. We're imposing by fiat that the square of a vector should be the quadratic form's value and seeing where it takes us. Treat x^2 = Q(x) as a symbolic rewriting rule that lets you replace x^2 or x x with Q(x) and vice versa whenever x is a vector. Beyond that Cl(V) satisfies the standard axioms of an algebra: it lets you multiply by scalars, it's associative and distributive, but not necessarily commutative.

Remarkably, this is all you need to derive everything about Clifford algebras.

Let me show you how easy it is to bootstrap the theory from nothing.

We know Cl(V) contains a copy of V. Since x^2 = Q(x) for all x, it must also contain a copy of some nonnegative reals.