Skip to content

Instantly share code, notes, and snippets.

View justinmeiners's full-sized avatar

Justin Meiners justinmeiners

View GitHub Profile

(Originally written as a reply to an HN submission of this article:

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:

markasoftware / html.lisp
Last active June 16, 2024 02:08
html->string (Super simple HTML templating for Lisp)
;; 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.")
(defvar *html-escapes*
'(#\> "&gt;"
// x64 encoding
enum Reg {
R8, R9, R10, R11, R12, R13, R14, R15,
enum XmmReg {
XMM8, XMM9, XMM10, XMM11, XMM12, XMM13, XMM14, XMM15,

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:

template <class _Ty>
_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;
frankus / Pure
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) {
shakna-israel /
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?

pgp44 / lttp.sql
Last active March 21, 2023 21:47
SQL implementation of Largest Triangle Three Bucket time series sampling algoritm
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 $$
when maxsurfacetriangle is null or triangle_surface(p1,p2,p3) > maxsurfacetriangle.surface
munificent / generate.c
Last active May 14, 2024 05:30
A random dungeon generator that fits on a business card
#include <time.h> // Robert Nystrom
#include <stdio.h> // @munificentbob
#include <stdlib.h> // for Ginny
#define r return // 2008-2019
#define l(a, b, c, d) for (i y=a;y\
<b; y++) for (int x = c; x < d; x++)
typedef int i;const i H=40;const i W
=80;i m[40][80];i g(i x){r rand()%x;
}void cave(i s){i w=g(10)+5;i h=g(6)
+3;i t=g(W-w-2)+1;i u=g(H-h-2)+1;l(u

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.