Skip to content

Instantly share code, notes, and snippets.

@Willmo36
Created December 3, 2018 18:27
Show Gist options
  • Save Willmo36/5a4dd5dbb2c1d5c66426057208c346f1 to your computer and use it in GitHub Desktop.
Save Willmo36/5a4dd5dbb2c1d5c66426057208c346f1 to your computer and use it in GitHub Desktop.
TypeScript (almost) point free Queue
import { head as headArr, reverse, snoc as snocArr, tail as tailArr } from "fp-ts/lib/Array";
import {
applyFlipped,
compose,
constant,
Curried2,
Curried3,
curry,
Endomorphism,
flip,
Function1,
Function2,
identity,
Predicate
} from "fp-ts/lib/function";
import { Option, option } from "fp-ts/lib/Option";
import { Lens } from "monocle-ts";
import { join } from "./FunctionMonad";
export type Queue<A> = {
f: A[];
t: A[];
};
//Wrap in a closure with paramm A to mimic existential type A
//unfortunately means executing all this per A
export function QueueOps<A>() {
const L = Lens.fromProp<Queue<A>>();
const empty: Queue<A> = {
f: [],
t: []
};
const altEmpty = AltEmpty<A>();
const clearT = L("t").set([]);
//join turns the Queue<A> -> Queue<A> -> Queue<A>
//into a Queue<A> -> Queue<A>
//fitting out compose
const moveTtoF = join<Queue<A>, Queue<A>>(
compose(
L("f").set,
<Function1<A[], A[]>>reverse,
L("t").get
)
);
// snocArr final form
// from (A[], A) -> A[]
// to A -> A[] -> A[]
const snocArr2 = flip(curry(<Function2<A[], A, A[]>>snocArr));
const isEmpty = compose(
f => f.length === 0,
L("f").get
);
const checkF = ifElse(
isEmpty,
compose(
clearT,
moveTtoF
),
identity
);
const head = compose<Queue<A>, A[], Option<A>>(
headArr,
L("f").get
);
const tail = compose(
checkF,
L("f").modify(
compose(
altEmpty,
tailArr
)
)
);
//constant(checkF) to turn a Q -> Q into A -> Q -> Q
const snoc = compose(
constant(checkF),
L("t").modify,
snocArr2
);
return { empty, isEmpty, head, tail, snoc };
}
function AltEmpty<A>() {
type F0 = typeof option.foldr;
type F1 = Curried3<Option<A[]>, A[], Endomorphism<A[]>, A[]>;
type F2 = Curried3<A[], Option<A[]>, Endomorphism<A[]>, A[]>;
type F3 = Curried2<Option<A[]>, Endomorphism<A[]>, A[]>;
type F4 = Curried2<Endomorphism<A[]>, Option<A[]>, A[]>;
type F5 = Function1<Option<A[]>, A[]>;
// const f1: F1 = curry(option.foldr);
// const f2: F2 = flip(f1);
// const f3: F3 = f2([]);
// const f4: F4 = flip(f3);
// const f5: F5 = f4(identity);
return compose<F0, F1, F2, F3, F4, F5>(
applyFlipped(identity),
flip,
applyFlipped([]),
flip,
curry
)(option.foldr);
}
//not sure how to PF this
//thinking of somethin like (fn, pred)[] -> filter -> head
const ifElse = <A, B>(p: Predicate<A>, trueFn: Function1<A, B>, falseFn: Function1<A, B>) => (
a: A
) => (p(a) ? trueFn(a) : falseFn(a));
//FunctionMonad.ts
import { compose, constant, Function1, identity } from "fp-ts/lib/function";
import { Monad2 } from "fp-ts/lib/Monad";
export const URI = "Function";
export type URI = typeof URI;
declare module "fp-ts/lib/HKT" {
interface URI2HKT2<L, A> {
Function: Function1<L, A>;
}
}
const map: Monad2<URI>["map"] = compose;
//TODO pf: The final frontier...
//p = flip flip id . (ap .) . flip (.)
const chain = <L, A, B>(fa: Function1<L, A>, f: (a: A) => Function1<L, B>) => (l: L) => f(fa(l))(l);
const ap = <L, A, B>(fab: Function1<L, (a: A) => B>, fa: Function1<L, A>) => (l: L) =>
fab(l)(fa(l));
type Join = <A, B>(ffa: Function1<A, Function1<A, B>>) => Function1<A, B>;
export const join: Join = ffa => chain(ffa, identity);
export const func: Monad2<URI> = {
URI,
of: constant,
map,
chain,
ap
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment