Skip to content

Instantly share code, notes, and snippets.

@raganwald
Last active August 5, 2025 12:16
Show Gist options
  • Save raganwald/6558ddfd76b16fe7b7213a80f54576e0 to your computer and use it in GitHub Desktop.
Save raganwald/6558ddfd76b16fe7b7213a80f54576e0 to your computer and use it in GitHub Desktop.
Mockingbirds and Why Birds as Higher-Kinded Types
// ---------- Mockingbirds and Why Birds with Higher-Kinded Types ----------
//
// The nicknames "Mockingbird" and "Why Bird" are derived from "To Mock a
// Mockingbird" by Raymond Smullyan.
//
// requires https://github.com/poteat/hkt-toolbelt
import { Kind, $, $$ } from "hkt-toolbelt";
import { _$inputOf } from "hkt-toolbelt/kind";
import { _$cast } from "hkt-toolbelt/type";
// a useful testing abbreviation
type Expect<T extends true> = T;
// A kind that takes a kind as its argument
export interface HigherOrderKind extends Kind.Kind {
f(
x: _$cast<this[Kind._], Kind.Kind>
): any
}
// ---------- The Mockingbird as an HKT ----------
//
// See "To Grok a Mockingbird:" https://raganwald.com/2018/08/30/to-grok-a-mockingbird.html
//
// const mockingbird = fn => (...args) => fn(fn, ...args);
export type _$M<K extends HigherOrderKind> =
K extends _$inputOf<K>
? $<K, K>
: never;
export interface M extends HigherOrderKind {
f(
x: _$cast<this[Kind._], HigherOrderKind>
): _$M<typeof x>
}
namespace TestM {
//@ts-expect-error should type error if it doesn't take a kind
type _0 = _$M<NaturalNumber.Decrement>
//@ts-expect-error should type error if it doesn't take a kind
type _1 = $<M, NaturalNumber.Decrement>
}
// ---------- The Why Bird as an HKT ----------
//
// This is a nearly direct translation of a JS
// implementation from "Why Y? Deriving the
// Y Combinator in JavaScript:"
//
// https://raganwald.com/2018/09/10/why-y.html
//
// const Y =
// fn =>
// M(m => a => fn(m(m))(a));
// A kind that encapsulates the "maker" function within the Why Brd
type _$Maker<FN extends HigherOrderKind, M extends HigherOrderKind, A> =
$< FN,_$cast<_$M<M>, _$inputOf<FN>> > extends infer InnerMaker extends Kind.Kind
? $< InnerMaker, _$cast<A, _$inputOf<InnerMaker>> >
: never;
interface Maker_T<FN extends HigherOrderKind, M extends HigherOrderKind> extends Kind.Kind {
f(
a: this[Kind._]
): _$Maker<FN, M, typeof a>
}
interface Maker<FN extends HigherOrderKind> extends Kind.Kind {
f(
m: _$cast<this[Kind._], HigherOrderKind>
): Maker_T<FN, typeof m>
}
// The Why Bird composes a decoupled recursive kind with itself,
// converting a decoupled recursive kind to a recurive kind
export type _$Y<FN extends HigherOrderKind> = _$M<Maker<FN>>;
export interface Y extends HigherOrderKind {
f(
fn: _$cast<this[Kind._], HigherOrderKind>
): _$Y<typeof fn>
}
import { Boolean, NaturalNumber } from "hkt-toolbelt";
namespace TestY {
// a decoupled recursive HKT for determining whether a natural number is even
// it is not written in tail-recursive form, but should be fine for testing
// whether Y works or not
type _$IsEvenDecoupled<Myself extends HigherOrderKind, N extends number> =
N extends 0
? true
: N extends 1
? false
: $$<[NaturalNumber.Decrement, Myself, Boolean.Not], N>;
interface IsEvenDecoupled_T<Myself extends HigherOrderKind> extends Kind.Kind {
f(
x: _$cast<this[Kind._], number>
): _$IsEvenDecoupled<Myself, typeof x>
}
// A recursive kind that is decoupled from itself is a higher-ordered
// kind because it is inherenetly paramaterized by a kind ("myself")
interface IsEvenDecoupled extends HigherOrderKind {
f(
x: _$cast<this[Kind._], Kind.Kind>
): IsEvenDecoupled_T<typeof x>
}
type IsEven = $<Y, IsEvenDecoupled>;
type _0 = Expect<$<IsEven, 0>>;
type _1 = Expect<$$<[IsEven, Boolean.Not], 1>>;
type _2 = Expect<$<IsEven, 2>>;
type _3 = Expect<$$<[IsEven, Boolean.Not], 3>>;
type _22 = Expect<$<IsEven, 22>>;
type _27 = Expect<$$<[IsEven, Boolean.Not], 25>>;
type _42 = Expect<$<IsEven, 42>>;
type _47 = Expect<$$<[IsEven, Boolean.Not], 47>>;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment