Изоморфизмы и программирование

Hillel Wayne, автор учебника по языку спецификаций TLA+, заметил закономерность: чем больше тренируешь способность формально рассуждать об изоморфизмах, тем чаще видишь, что вроде бы несвязанные вещи на деле эквивалентны. В проектировании API это рабочий инструмент. Берёшь интерфейс, с которым неудобно работать, и переписываешь в эквивалентный, с которым проще. Форма типа меняется, информация внутри остаётся та же.

Этот урок не про синтаксис TypeScript. Он про оптику, через которую ты смотришь на типы и структуры данных. После него ты будешь замечать, что T | null и Option<T> это одно и то же, что два аргумента и пара это одно и то же, а набор булевых флагов часто прячет внутри размеченное объединение.

Изоморфизм для программиста

Возьмём строку и список её символов.

const s1 = 'abc';
const s2 = [...s1]; // ['a', 'b', 'c'], то же что Array.from(s1)
const s3 = s2.join(''); // 'abc'

Две функции, split (тут это [...s], расщепление строки в массив символов) и join, обратны друг другу. Прогон строки туда и обратно возвращает ту же строку.

[...s1].join('') === s1; // true

Допустим, мы хотим обработать список символов так, чтобы все они оказались в верхнем регистре. Кто немного владеет функциональным стилем, запишет через map.

const s2 = [...'abc'];
s2.map((c) => c.toUpperCase()); // ['A', 'B', 'C']

Но мы можем сделать то же самое и через строку: склеить список обратно, поднять регистр у целой строки, снова расщепить.

[...'abc'.toUpperCase()]; // ['A', 'B', 'C']

Оба пути дают одинаковый результат.

[...'abc'.toUpperCase()].join('') === [...'abc'].map((c) => c.toUpperCase()).join('');
// true

Тут есть некоторая строковая трансформация ts (например, toUpperCase для строки) и соответствующая ей трансформация списка tl (тот же toUpperCase, но поэлементно через map). Так, что для любой строки s:

join( map(tl, split(s)) ) === ts(s)

Когда из двух структур можно так свободно ходить туда-сюда без потери информации, говорят, что строки и списки изоморфны друг другу (в контексте данных трансформаций ts и tl). Изоморфизм это не про «равны», а про «взаимно переводимы один в один».

Поиграй с квадратом

Введи строку, выбери трансформацию и посмотри, сойдутся ли оба пути. UPPER и rot13 поэлементные, квадрат коммутирует. А вот reverse действует на структуру, а не на отдельные символы, и у него нет поэлементного двойника: map не умеет переставлять элементы местами. Квадрат расходится, и это важная граница.

UPPERrot13reverse

split(s)

map(t)→

map(t)(split(s))

↑split

≅

↓join

s

t→

t(s)

То, что reverse ломает диаграмму, не баг, а ровно тот сигнал, который нам и нужен. Изоморфизм строк и списков переносит только те трансформации, которые поэлементны. Перестановки, вставки, любые операции над порядком живут на уровне структуры, а не элементов, и их через map не выразить.

Биекция: один к одному

Прежде чем разбирать изоморфизм формально, нужны два кирпича. Первый это биекция.

Биекция между типами T и U это пара функций to: T => U и from: U => T, таких что from(to(x)) === x и to(from(y)) === y. Ни один элемент не теряется и не склеивается с другим. Именно поэтому split и join образуют биекцию между строками и списками односимвольных строк.

const to = (s: string): string[] => [...s];
const from = (xs: string[]): string => xs.join('');

from(to('abc')) === 'abc'; // true (round-trip туда и обратно)

Биекция это обратимость. Но обратимости мало: важно ещё, чтобы функция уважала операции над типами. Это второй кирпич.

Гомоморфизмы

Гомоморфизм чуть хитрее биекции. Допустим, для наших типов определены бинарные операции:

(+) : (T, T) => T
(*) : (U, U) => U

Тогда функция f: T => U называется гомоморфной, если она переводит первую операцию во вторую:

f(a + b) === f(a) * f(b)

Иначе говоря, неважно, сначала ли ты соединил два значения слева и перевёл результат, или сначала перевёл оба по отдельности, а потом соединил справа. Получится одно и то же.

Пример. Пусть + это обычная конкатенация строк, а * это конкатенация списков (через concat). Тогда split гомоморфна:

const split = (s: string): string[] => [...s];

const left = split('abc' + 'def'); // split целого
const right = split('abc').concat(split('def')); // склейка двух split

left.join() === right.join(); // true: ['a','b','c','d','e','f']

Взятие длины length это тоже гомоморфизм, но уже между строками и числами: слева конкатенация, справа сложение.

('abc' + 'def').length === 'abc'.length + 'def'.length; // true: 6 === 3 + 3

length теряет почти всю информацию о строке, но одну вещь сохраняет идеально: как складываются длины при склейке. Это и есть суть гомоморфизма, сохранять конкретную структуру, а не всё подряд.

Ещё пример, ближе к геометрии. Если мы хотим представить точку на плоскости как точку в пространстве, гомоморфизм из 2D в 3D добавляет нулевую координату, а обратный отбрасывает её.

type P2 = { x: number; y: number };
type P3 = { x: number; y: number; z: number };

const to3 = ({ x, y }: P2): P3 => ({ x, y, z: 0 });
const to2 = ({ x, y, z: _z }: P3): P2 => ({ x, y });

Подумай сам, прежде чем читать дальше: изоморфны ли такие 2D и 3D точки? Ответ будет ниже, и он показывает, зачем нам вообще понятие подмножества.

Изоморфизм = биективный гомоморфизм

Теперь собираем определение целиком.

Изоморфизм между двумя типами это биективный гомоморфизм.

Биективный означает обратимость один к одному (раскладку каждого элемента справа на соответствующий элемент слева). Гомоморфный означает, что отображение уважает операции. Когда оба свойства выполняются разом, два типа неотличимы с точки зрения тех операций, ради которых мы их рассматриваем. Можно жить в любом из них и переезжать туда-сюда без потерь.

Вернёмся к строкам и спискам. Строго говоря, изоморфизм здесь это не сама пара трансформаций ts и tl, а лежащая под ними пара split и join. Они образуют биективный гомоморфизм моноидов над операцией конкатенации.

Моноид это просто тип с операцией склейки и нейтральным элементом. У строк это + и ''. У списков это concat и []. split и join не только взаимно обратны (биекция), но и переводят склейку строк в склейку списков (гомоморфизм), да ещё уважают нейтральный элемент: split('') === []. Если для тебя «биективный гомоморфизм моноидов» пока бессмысленный набор слов, не переживай: за ним стоит ровно то, что ты уже видел в квадрате. Слова это просто точное имя для интуиции.

Тот же принцип работает в гомоморфном шифровании: оно допускает вычисления над зашифрованными данными без расшифровки. Название не случайно: шифрование там это гомоморфизм, переводящий операцию над открытым текстом в операцию над шифротекстом.