Last active
August 5, 2025 12:16
-
-
Save raganwald/6558ddfd76b16fe7b7213a80f54576e0 to your computer and use it in GitHub Desktop.
Mockingbirds and Why Birds as Higher-Kinded Types
This file contains hidden or 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
// ---------- 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