Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Experiment with modelling Higher Kinded Types (HKTs) in TypeScript
interface HKT<F, A> {
__hkt: [F, A];
}
namespace FunctorNS {
export interface Functor<F, A> extends HKT<F, A> {
map<B>(f: (a: A) => B): Functor<F, B>;
}
export const map = <F, A, B>(
fn: (a: A) => B,
functor: Functor<F, A>,
): Functor<F, B> => functor.map(fn);
}
// Identity
namespace IdentityNS {
import Functor = FunctorNS.Functor;
export type IdentityType = 'Identity';
export class Identity<A> implements Functor<IdentityType, A> {
__hkt: [IdentityType, A];
constructor(readonly value: A) {}
map<B>(f: (a: A) => B): Identity<B> {
return new Identity(f(this.value));
}
}
export const identity = <A>(value: A) => new Identity<A>(value);
}
// Binary Tree
namespace BinaryTreeNS {
import Functor = FunctorNS.Functor;
export type BinaryTreeType = 'BinaryTree';
export class BinaryNode<A> implements Functor<BinaryTreeType, A> {
__hkt: [BinaryTreeType, A];
constructor(
readonly left: BinaryTree<A>,
readonly value: A,
readonly right: BinaryTree<A>,
) {}
map<B>(f: (a: A) => B): BinaryTree<B> {
return new BinaryNode(this.left.map(f), f(this.value), this.right.map(f));
}
}
export class BinaryLeaf<A> implements Functor<BinaryTreeType, A> {
__hkt: [BinaryTreeType, any];
map<B>(f: (a: A) => B): BinaryTree<B> {
return leaf;
}
}
export type BinaryTree<A> = BinaryNode<A> | BinaryLeaf<A>;
export const node = <A>(
left: BinaryTree<A>,
value: A,
right: BinaryTree<A>,
) => new BinaryNode<A>(left, value, right);
export const leaf = new BinaryLeaf<any>();
}
namespace App {
import BinaryTree = BinaryTreeNS.BinaryTree;
import node = BinaryTreeNS.node;
import leaf = BinaryTreeNS.leaf;
import map = FunctorNS.map;
const tree: BinaryTree<string> = node(
leaf,
'a',
node(leaf, 'ab', node(leaf, 'abc', leaf)),
);
const len = (s: string): number => s.length;
console.log(map(len, tree));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment