Функциональное программирование на TypeScript: полиморфизм родов высших порядков

Привет, Хабр! Меню зовут Юрий Богомолов, и вы (возможно) можете меня знать по моей работе над серией #MonadicMondays в твиттере, по каналу на ютьюбе или статьям на Medium или dev.to. В русскоязычном сегменте интернета очень мало информации по функциональному программированию на TypeScript и одной из лучших экосистем для этого языка — библиотеке fp-ts, в экосистему которой я достаточно активно контрибьютил некоторое время назад. Этой статьей я хочу начать рассказ о ФП на TypeScript, и если будет положительный отклик от хабрасообщества, то продолжу серию.

Думаю, ни для кого не станет откровением то, что TypeScript является одним из самых популярных надмножеств JS со строгой типизацией. После включения строгого режима компиляции и настройки линтера на запрет использования any этот язык становится пригодным для промышленной разработки во многих сферах — от CMS до банковского и брокерского ПО. Для системы типов TypeScript были даже неофициальные попытки доказательства полноты по Тьюрингу, что позволяет применять продвинутые техники тайп-левел программирования для обеспечения корректности бизнес-логики при помощи техник «making illegal states unrepresentable».

Всё вышеперечисленное дало толчок к созданию для TypeScript замечательной библиотеки для функционального программирования — fp-ts за авторством итальянского математика Джулио Канти. Одна из первых вещей, с которой сталкивается человек, желающий ее освоить, — весьма специфичные определения типов вида Kind<URI, SomeType> или interface SomeKind<F extends URIS> {}. В этой статье я хочу подвести читателя к пониманию всех этих «сложностей» и показать, что на самом деле всё очень просто и понятно — стоит только начать раскручивать этот паззл.

Когда заходит речь о функциональном программировании, то разработчики на JS обычно останавливаются на композиции чистых функций и написании простых комбинаторов. Немногие заглядывают на территорию функциональной оптики, и практически невозможно встретить заигрывания с фримонадическими API или схемами рекурсии. На деле же все эти конструкции не являются чем-то неподъемно-сложным, и система типов сильно облегчает изучение и понимание. TypeScript как язык обладает достаточно богатыми выразительными возможностями, однако у них есть свой предел, который доставляет неудобства — отсутствие родов/кайндов/kinds. Чтобы было понятнее, давайте рассмотрим пример.

Возьмем всем привычный и хорошо изученный массив. Массив, как и список, — это структура данных, выражающая идею недетерминированности: в нем может храниться от 0 до N элементов определенного типа A. При этом, если у нас есть функция вида A -> B, мы можем «попросить» этот массив применить ее с помощью вызова метода .map(), получив на выходе массив того же размера с элементами типа B, следующими в том же порядке, что и в оригинальном массиве:

const as = [1, 2, 3, 4, 5, 6]; // as :: number[]
const f = (a: number): string => a.toString();

const bs = as.map(f); // bs :: string[]
console.log(bs); // => [ '1', '2', '3', '4', '5', '6' ]

Проведем мысленный экперимент. Вынесем функцию map из прототипа массива в отдельный интерфейс. В итоге мы получаем полиморфную по типу входного и выходного типа функцию высшего порядка, которую я сразу сделаю каррированной для простоты дальнейшего чтения:

interface MappableArray {
  readonly map: <A, B>(f: (a: A) => B) => (as: A[]) => B[];
}

Вроде бы всё хорошо. Но если мы продолжим наш мысленный эксперимент и начнем рассматривать другие структуры данных, то очень быстро поймем, что функцию map можно реализовать для множества (Set), или хэш-таблицы (Map), или дерева, или стека, или… Много для чего, в общем. Давайте посмотрим, как будут меняться сигнатуры функций map для упомянутых структур данных:

type MapForSet   = <A, B>(f: (a: A) => B) => (as: Set<A>) => Set<B>;
type MapForMap   = <A, B>(f: (a: A) => B) => (as: Map<string, A>) => Map<string, B>;
type MapForTree  = <A, B>(f: (a: A) => B) => (as: Tree<A>) => Tree<B>;
type MapForStack = <A, B>(f: (a: A) => B) => (as: Stack<A>) => Stack<B>;

Для простоты я зафиксировал у хэш-таблицы Map строковый тип ключа, чтобы подчеркнуть, что мы рассматриваем ее как полиморфную по типу данных, исключая на текущий момент из рассмотрения полиморфизм по типу ключа.

Думаю, вы уже увидели общий паттерн и задумались: как бы можно было абстрагироваться от типа структуры данных и написать некий обобщенный интерфейс Mappable. Для такой абстракции необходимо, чтобы язык полноценно поддерживал роды высшего порядка, то есть чтобы можно было абстрагироваться от конструкторов типов. Переводя на терминологию TypeScript, нужно иметь возможность написать интерфейс, который может в качестве дженерик-аргументов принимать другие дженерик-типы:

interface Mappable<F> {
  // Type 'F' is not generic. ts(2315)
  readonly map: <A, B>(f: (a: A) => B) => (as: F<A>) => F<B>;
}

К сожалению, этот код не скомпилируется, потому что TypeScript не знает, что тип-аргумент F должен быть дженериком. Мы не можем написать как в Scala F<_> или как-либо еще — в языке просто нет выразительных средств для этого. Значит ли это, что нужно опустить руки и дублировать код? Нет, на выручку приходит замечательная академическая статья «Легковесный полиморфизм родов высшего порядка».

Для того, чтобы сэмулировать в TypeScript полиморфизм родов, мы применим технику, которая называется «дефункционализация» — техника перевода программ высшего порядка на язык первого порядка. Проще говоря — вызовы функций превращаются в вызов конструкторов данных с аргументами, соответствующими аргументам функций. В дальнейшем такие конструкторы сопоставляются с образцом (pattern-matching) и интерпретируются уже по месту необходимости. Для тех, кто захочет глубже разобраться в теме, советую оригинальную статью Джона Рейнолдса «Definitional interpreters for higher-order programming languages», а мы тем временем посмотрим, как эту технику можно применить к эмуляции родов.

Итак, мы хотим выразить следующую идею: есть тип-дженерик Mappable, принимающий в качестве аргумента некую тип-переменную F, которая сама является конструктором типов первого порядка, то есть дженериком, принимающим в качестве аргумента обычный не-полиморфный тип. Применяя технику дефункционализации, мы сделаем следующее:

1. Тип-переменную F заменим на уникальный идентификатор типа — некий строковый литерал, который будет однозначно указывать, какой конструктор типа мы хотим вызвать: 'Array', 'Promise', 'Set', 'Tree' и так далее.
2. Создадим служебный тип-конструктор Kind<IdF, A>, который будет представлять собой вызов типа F как дженерика с аргументом типа A: Kind<'F', A> ~ F<A>.
3. Для упрощения интерпретации конструкторов Kind заведем набор типов-словарей, где будут храниться соотношения между идентификатором типа и самим полиморфным типом — по одному такому словарю для типов каждой арности.

Посмотрим, как это выглядит на практике:

interface URItoKind<A> {
  'Array': Array<A>;
} // словарь для типов 1-арности: Array, Set, Tree, Promise, Maybe, Task...
interface URItoKind2<A, B> {
  'Map': Map<A, B>;
} // словарь для типов 2-арности: Map, Either, Bifunctor...

type URIS = keyof URItoKind<unknown>; // тип-сумма всех «имён» типов 1-арности
type URIS2 = keyof URItoKind2<unknown, unknown>; // все типы 2-арности
// и так далее, сколько сочтете нужным

type Kind<F extends URIS, A> = URItoKind<A>[F];
type Kind2<F extends URIS2, A> = URItoKind2<A>[F];
// и так далее

Остается дело за малым: дать возможность пополнять словари URItoKindN любым программистам, а не только авторам библиотеки, в которой применяется эта техника. И тут на выручку приходит замечательная возможность TypeScript, которая называется дополнением модулей (module augmentation). Благодаря ней нам достаточно будет разместить код с дефункционализированными родами в основной библиотеке, а из пользовательского кода определение типа высшего порядка будет простым:

type Tree<A> = ...

declare module 'my-lib/path/to/uri-dictionaries' {
  interface URItoKind<A> {
    'Tree': Tree<A>;
  }
}

type Test1 = Kind<'Tree', string> // сразу же выведется в Tree<string>

Теперь мы можем определить наш тип Mappable по-настоящему — полиморфно для любых 1-арных конструкторов, и реализовать его экземпляры для разных структур данных:

interface Mappable<F extends URIS> {
  readonly map: <A, B>(f: (a: A) => B) => (as: Kind<F, A>) => Kind<F, B>;
}

const mappableArray: Mappable<'Array'> = {
  // здесь `as` будет иметь тип A[], без какого-либо упоминания служебного конструктора `Kind`:
  map: f => as => as.map(f)
};
const mappableSet: Mappable<'Set'> = {
  // немного нечестно — можно сделать эффективнее, перебирая итератор для множества вручную,
  // но цель этой статьи не сделать максимально эффективную реализацию, а объяснить концепцию
  map: f => as => new Set(Array.from(as).map(f))
};
// здесь я предположу, что Tree — обычный индуктивный тип с двумя конструкторами: листом и узлом,
// в листах хранятся данные, в узлах хранится набор поддеревьев:
const mappableTree: Mappable<'Tree'> = {
  map: f => as => {
    switch (true) {
      case as.tag === 'Leaf': return f(as.value);
      case as.tag === 'Node': return node(as.children.map(mappableTree.map(f)));
    }
  }
};

Наконец, я могу сорвать маску с типа Mappable и сказать, что он называется Functor. Функтор состоит из типа T и операции fmap, которая позволяет при помощи функции A => B преобразовать T<A> в T<B>. Еще можно сказать, что функтор поднимает функцию A => B в некий вычислительный контекст T (этот взгляд очень пригодится в дальнейшем, когда будем разбирать тройку Reader/Writer/State).

Собственно, идея дефункционализации и легковесного полиморфизма родов высшего порядка стала ключевой для библиотеки fp-ts. Джулио написал прагматичный и лаконичный гайд о том, как определять свои типы высшего порядка: https://gcanti.github.io/fp-ts/guides/HKT.html. Поэтому нет нужды каждый раз применять дефункциолизацию в своих программах — достаточно подключить fp-ts и положить идентификаторы типов в словари URItoKind/URItoKind2/URItoKind3, находящиеся в модуле fp-ts/lib/HKT.

В экосистеме fp-ts есть много замечательных библиотек:

• io-ts — библиотека для написания рантайм-валидаторов типов с синтаксисом, максимально близким к синтаксису типов TS
• parser-ts — библиотека парсерных комбинаторов, эдакий parsec на минималках
• monocle-ts — библиотека для функциональной оптики, порт скаловской библиотеки monocle на TS
• remote-data-ts — библиотека с контейнерным типом RemoteData, существенно упрощающим безопасную обработку данных на фронте
• retry-ts — библитека с комбинаторами разных стратегий повтора монадических операций
• elm-ts — микро-фреймворк для программирования в духе Elm Architecture на TS
• waveguide, matechs-effect — системы очень мощных алгебраических эффектов для TS, вдохновленных ZIO

Ну и мои библиотеки из ее экосистемы:

• circuit-breaker-monad — паттерн Circuit Breaker с монадическим интерфейсом
• kleisli-ts — библиотека для программирования с помощью стрелок Клейсли, вдохновленная ранним дизайном ZIO
• fetcher-ts — враппер вокруг fetch, поддерживающий валидацию ответа сервера с помощью типов io-ts
• alga-ts — порт замечательной библиотеки для описания алгебраических графов alga на TS

---

На этом введение я бы хотел завершить. Напишите, пожалуйста, в комментариях, насколько такой материал интересен лично вам. Я сделал уже несколько итераций преподавания этого материала, и каждый раз находил моменты, которые можно улучшить. Учитывая техническую продвинутость аудитории Хабра, возможно, нет смысла объяснять на Mappable/Chainable и т.д., а сразу называть вещи своими именами — функтор, монада, аппликатив? Пишите, буду рад пообщаться в комментариях.

Let's block ads! (Why?)