Skip to content

Instantly share code, notes, and snippets.

@ENvironmentSet
Last active December 30, 2020 11:13
Show Gist options
  • Save ENvironmentSet/be7cee44d5d2605059376673c834a769 to your computer and use it in GitHub Desktop.
Save ENvironmentSet/be7cee44d5d2605059376673c834a769 to your computer and use it in GitHub Desktop.
ST Monad In Typescript
// Sorry for poor naming, this example was intented to explain how to use skolem capturing in practise.
interface Stateful<S, A> {
(state: S): [A, S]
}
function fmap<S, A, B>(f: (a: A) => B): (stateful: Stateful<S, A>) => Stateful<S, B> {
return stateful => state => {
const [a, nextState] = stateful(state);
return [f(a), nextState];
}
}
function pure<S, A>(a: A): Stateful<S, A> {
return state => [a, state];
}
function ap<S, A, B>(statefulF: Stateful<S, (a: A) => B>): (stateful: Stateful<S, A>) => Stateful<S, B> {
return stateful => state => {
const [f, currentState] = statefulF(state);
const [a, nextState] = stateful(currentState);
return [f(a), nextState];
}
}
function bind<S, A, B>(stateful: Stateful<S, A>): (stateF: (a: A) => Stateful<S, B>) => Stateful<S, B> {
return stateF => state => {
const [a, nextState] = stateful(state);
return stateF(a)(nextState);
}
}
function then<S, A, B>(_: Stateful<S, A>): (stateful: Stateful<S, B>) => Stateful<S, B> {
return stateful => stateful;
}
function runStateful<A>(cont: <S>() => Stateful<S, A>): A {
const stateP = Symbol('State#');
return cont()(stateP)[0];
}
type NominallyTyped<T, N> = T & { readonly _nominalTag: (n: N) => N };
type STRef<S, A> = NominallyTyped<{ ref: A }, S>;
function stRef<S, A>(ref: A): STRef<S, A> {
return {
ref
} as STRef<S, A>;
}
function newSTRef<S, A>(value: A): Stateful<S, STRef<S, A>> {
return pure(stRef(value));
}
function readSTRef<S, A>({ ref }: STRef<S, A>): Stateful<S, A> {
return pure(ref);
}
function writeSTRef<S, A>(stRefA: STRef<S, A>): (a: A) => Stateful<S, void> {
return a => {
stRefA.ref = a;
return pure(undefined);
}
}
// examples
runStateful<number>(<S>() =>
bind<S, STRef<S, number>, number>(
newSTRef(0))
(ref => then<S, void, number>(writeSTRef(ref)(1))(readSTRef(ref)))
) + 2;
runStateful(<S>() => newSTRef<S, number>(0));
type NominallyTypedWithPhantom<T, N> = T & PhantomTypeParameter<N>;
abstract class PhantomTypeParameter<P> {
protected abstract _nominalTag(p: P): P
}
type ST<S, A> = NominallyTypedWithPhantom<{ readonly value: A }, S>;
function st<S, A>(value: A): ST<S, A> {
return {
value,
} as ST<S, A>;
}
st.map = <S, A, B>(f: (a: A) => B) => ({ value }: ST<S, A>) => st<S, B>(f(value));
st.ap = <S, A, B>({ value: f }: ST<S, (a: A) => B>) => ({ value }: ST<S, A>) => f(value);
st.bind = <S, A, B>({ value }: ST<S, A>) => (f: (a: A) => ST<S, B>) => f(value);
st.then = <S, A, B>(_: ST<S, A>) => (stB: ST<S, B>) => stB;
function runST<A>(cont: <S>() => ST<S, A>): A {
return cont().value;
}
type STRef<S, A> = NominallyTypedWithPhantom<{ ref: A }, S>;
function stRef<S, A>(ref: A): STRef<S, A> {
return {
ref
} as STRef<S, A>;
}
function newSTRef<S, A>(value: A): ST<S, STRef<S, A>> {
return st(stRef(value));
}
function readSTRef<S, A>({ ref }: STRef<S, A>): ST<S, A> {
return st(ref);
}
function writeSTRef<S, A>(stRefA: STRef<S, A>): (a: A) => ST<S, void> {
return a => {
stRefA.ref = a;
return st(undefined);
}
}
// examples
runST<number>(<S>() =>
st.bind<S, STRef<S, number>, number>(
newSTRef(0))
(ref => st.then<S, void, number>(writeSTRef(ref)(1))(readSTRef(ref)))
) + 2;
runST(<S>() => st.bind(newSTRef<S, boolean>(true))(readSTRef));
@ENvironmentSet
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment