Clever Geek Handbook

Functional Programming in TypeScript: Higher-Order Gender Polymorphism

Hello, Habr! Menu name is Yuri Bogomolov, and you (probably) can know me for my work on a series of #MonadicMondays tweeted on the channel on yutyube or articles to Medium or dev.to . In the Russian-speaking segment of the Internet, there is very little information on functional programming in TypeScript and one of the best ecosystems for this language - the fp-ts library , to the ecosystem of which I actively contributed some time ago. With this article I want to start a story about FP in TypeScript, and if there is a positive response from the Habra community, I will continue the series.



I don't think it will be a revelation to anyone that TypeScript is one of the most popular strongly typed supersets of JS. After enabling the strict compilation mode and setting the linter to prohibit use, anythis language becomes suitable for industrial development in many areas - from CMS to banking and brokerage software. For the TypeScript type system, there have even been unofficial attempts to prove Turing completeness, which allows advanced type-level programming techniques to be applied to ensure the correctness of business logic by making illegal states unrepresentable.



All of the above gave impetus to the creation of a wonderful library for TypeScript for functional programming - fp-tsby the Italian mathematician Giulio Canti. One of the first things that a person who wants to master it encounters is the very specific definitions of the types of the species Kind<URI, SomeType>or interface SomeKind<F extends URIS> {}. In this article, I want to lead the reader to understanding all these "complexities" and show that in fact everything is very simple and clear - you just need to start unwinding this puzzle.



Childbirth of a higher order



When it comes to functional programming, JS developers usually stop at composing pure functions and writing simple combinators. Few look into the territory of functional optics, and it is almost impossible to come across flirting with freemonadic APIs or recursion schemes. In fact, all of these constructions are not overly complex, and the type system greatly facilitates learning and understanding. TypeScript as a language has quite rich expressive capabilities, however, they have their own limit, which is inconvenient - the absence of genders / cinds / kinds. To make it clearer, let's look at an example.



. , , โ€” , : 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, B> = URItoKind2<A, B>[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



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



, fp-ts. , : https://gcanti.github.io/fp-ts/guides/HKT.html. โ€” fp-ts URItoKind/URItoKind2/URItoKind3, fp-ts/lib/HKT.



fp-ts :





:







. , , , . , , . , , Mappable/Chainable .., โ€” , , ? , .



More articles:


All Articles