Implementing a FingerTree in TypeScript with fp-ts

FingerTree.ts

/* References
   https://apfelmus.nfshost.com/articles/monoid-fingertree.html
   https://abhiroop.github.io/Finger-Trees/
   https://chrispenner.ca/posts/intro-to-finger-trees
   http://www.staff.city.ac.uk/~ross/papers/FingerTree.html
*/

import { Monoid } from "fp-ts/lib/Monoid";
import { Newtype, iso } from "newtype-ts";
import { Predicate } from "fp-ts/lib/function";
import { none, some } from "fp-ts/lib/Option";

export interface Measured<A, B> extends Monoid<B> {
    measure: (a: A) => B;
}

//#region Size
type Size = Newtype<"Size", number>;
const Size = iso<Size>();

export const monoidSize: Monoid<Size> = {
    empty: Size.wrap(0),
    concat(a, b) {
        return Size.wrap(Size.get(a) + Size.get(b));
    }
};

export const getMeasuredSize = <A>(): Measured<A, Size> => ({
    ...monoidSize,
    measure: a_ => Size.wrap(1)
});
//#endregion

//#region Priority
type Priority = Newtype<"Priority", number>;
const Priority = iso<Priority>();

export const monoidPriority: Monoid<Priority> = {
    empty: Priority.wrap(Infinity),
    concat(a, b) {
        return Priority.wrap(Math.min(Priority.get(a), Priority.get(b)));
    }
};

export const getMeasuredPriority = <A>(): Measured<A, Priority> => ({
    ...monoidPriority,
    measure: a_ => Priority.wrap(1) //todo implement priority function
});
//#endregion

//#region FingerTree
const URI = "FingerTree";
type URI = typeof URI;

export type FingerTree<A, M> = Branch<A, M> | Leaf<A, M>;

export class Branch<A, M> {
    readonly _tag: "Branch" = "Branch";
    readonly _A!: A;
    readonly _URI!: URI;
    public measure!: M;
    constructor(
        measured: Measured<A, M>,
        public readonly l: FingerTree<A, M>,
        public readonly r: FingerTree<A, M>
    ) {
        this.measure = measured.concat(this.l.measure, this.r.measure);
    }

    head(): A {
        return this.l.head();
    }

    isLeaf(): this is Leaf<A, M> {
        return false;
    }
}

export class Leaf<A, M> {
    readonly _tag: "Leaf" = "Leaf";
    readonly _A!: A;
    readonly _URI!: URI;
    public measure!: M;
    constructor(measured: Measured<A, M>, public readonly val: A) {
        this.measure = measured.measure(val);
    }

    head() {
        return this.val;
    }

    isLeaf(): this is Leaf<A, M> {
        return true;
    }
}

export const getMeasuredFingerTree = <A, M>(
    measured: Measured<A, M>
): Measured<FingerTree<A, M>, M> => ({
    empty: measured.empty,
    concat(a, b) {
        return a; //todo
    },
    measure(a) {
        return a.measure;
    }
});
//#endregion

type List<A> = FingerTree<A, Size>;
type PriorityQueue<A> = FingerTree<A, Priority>;

export const search = <A, M>(measuredA: Measured<A, M>, p: Predicate<M>) => (
    t: FingerTree<A, M>
) => {
    const go = (i: M, t: FingerTree<A, M>): A => {
        //inner basecase
        //we've worked our way to this leaf, it must fit the prior predicates
        if (t.isLeaf()) {
            return t.val;
        }

        //Determine which half of the tree the value lies in
        //concat moves i to the middle(t.l, t.r)
        const i2 = measuredA.concat(i, t.l.measure);
        const leftContainsFlip = p(i2);

        return leftContainsFlip ? go(i, t.l) : go(i2, t.r);
    };

    //basecase -- the predicate is true for the total measurement of the tree
    //confirming that it flips from false at somepoint within the tree
    const flips = p(t.measure);
    return flips ? some(go(measuredA.empty, t)) : none;
};

export const atIndex = <A>(p: Predicate<Size>) => search(getMeasuredSize<A>(), p);
atIndex(s => Size.unwrap(s) > 3);
/**
 * search walkthrough
 * p = s > 2 "Find the first item at index 3"
 * t =
 *     4
 *   2   2
 * 1 1  1 1
 * These numbers are the Size measure of each leaf/branch
 * 
 * the call to go starts with the empty Size, which is 0
 * 1a. target = 0, t =    4
                        2   2
                       1 1 1 1

    1b. Combine target with the measure of the left tree to get the middle :  0 + 2 = 2
    1c. Test the predicate: 2 > 3 = false
    1d. go down the right side, using the updated target (2)

    2a. target = 2, t = 2
                   1 1
    2b. combine target with the measure of the left tree to get the middle :  2 + 1 = 3
    2c. Test the predicate: 3 > 3 = true
    2d. go down the left hand side, using the original target (2)

    2a. target = 2, t = 1
    2b. Tree is a leaf, we're done!
 */