A JavaScript port of Data.Trie

trie.js

// Likely VERY inefficient port of Data.Trie
function Trie(a) {
    // could null be a valid value? if so, we can't use S.toMaybe
    this.value = S.toMaybe(a);
    this.children = {};
    this.ks = Object.freeze(this.value.isNothing ? [] : ['']);
};

/* Setoid */
// Trie a ~> Trie a -> Bool
Trie.prototype.equals = function equals(o) {
    return S.equals(this.toObject(), o.toObject());
};

/* Semigroup */
// Trie a ~> Trie a -> Trie a
Trie.prototype.concat = function concat(o) {
    return Trie.fromObject(S.concat(this.toObject(), o.toObject()));
};

/* Apply */
// Trie a ~> Trie (a -> b) -> Trie b
// Trie.prototype.ap = function ap(o) {};

/* Applicative */
// a -> Trie a
Trie.of = a => new Trie(a);

/* Chain */
// Trie a ~> (a -> Trie b) -> Trie b
// Trie.prototype.chain = function (f) {};

/* Functor */
// Trie a ~> (a -> b) -> Trie b
Trie.prototype.map = function map(f) {
    return Trie.fromObject(
        this.ks.reduce((o, k) => (o[k] = f(this.find(k)), o), {}));
};

/* Foldable */
// reduce :: Trie a ~> ((b, a) -> b, b) -> b
// Trie.prototype.reduce = function reduce(f, init) {};

/* Traversable */
// traverse :: Applicative f => Trie a ~> (TypeRep f, a -> f b) -> f (Trie b)
// Trie.prototype.traverse = function traverse(T, f) {};

/* Show */
// Trie a ~> String
Trie.prototype.toString = function toString() {
    const stringRep = S.toString(this.toObject());
    return `Trie(${stringRep.slice(1, stringRep.length-1)})`;
};

/* Basic functions */

/* Monoid */
// Trie a
Trie.empty = () => new Trie();

// Trie a ~> Bool
Trie.prototype.isEmpty = function isEmpty() {
    return this.ks.length === 0;
};

// String -> a -> Trie a
Trie.from = (k, a) => Trie.empty().insert(k, a);

// Trie a ~> Int
Trie.prototype.size = function size() {
    return this.ks.length;
};

/* Conversion functions */

// [[String, a]] -> Trie a
Trie.fromArray = ([[k, v], ...ps]) => Trie
    .from(k, v)
    .concat(ps.length > 0 ? Trie.fromArray(ps) : Trie.empty());

// Object a -> Trie a
Trie.fromObject = o => Object
    .keys(o)
    .reduce((root, k) => root.insert(k, o[k]), Trie.empty());

// Trie a ~> [String]
Trie.prototype.keys = function keys() {
    return this.ks;
};

// Trie a ~> (String -> a -> b) -> [b]
Trie.prototype.toArrayBy = function toArrayBy(f) {
    // this.toArray().map(([k, v]) => f(k)(v));
    return this.ks.reduce((bs, k) => [...bs, f(k)(this.find(k))], []);
};

// Trie a ~> [[String, a]]
Trie.prototype.toArray = function toArray() {
    return this.toArrayBy(k => b => [k, b]);
    // return this.ks.reduce((o, k) => [k, this.find(k).value], []);
};

// Trie a ~> [a]
Trie.prototype.values = function values() {
    return this.ks.map(k => this.find(k).value);
};

// Trie a ~> Object a
Trie.prototype.toObject = function toObject() {
    return this.ks.reduce((o, k) => (o[k] = this.find(k).value, o), {});
};

/* Query methods */
function findBy_(m_t_b, b, t_b) {
    return mA => tA => {
        const [k, ...ks] = mA.isNothing ? '' : mA.value;
        return k === undefined ? tA.value :
            k in tA.children ?
            findBy_(m_t_b, b, t_b)(S.Just(ks))(tA.children[k]) :
            b;
    };
}

// Trie a ~> (Maybe a -> Trie a -> b) -> (String -> b)
Trie.prototype.findBy = function findBy(f) {
    return S.flip(
        findBy_(f,
                f(S.Nothing)(Trie.empty()),
                f(S.Nothing))
    )(this);
};

// I'll probably end up using the commented-out implementation below for efficiency.
// Trie a ~> String -> Maybe a
Trie.prototype.find = function find(k) {
    return findBy_(S.K, S.Nothing, S.K(S.Nothing))(S.Just(k))(this);
    // return k === undefined ? this.value :
    //     k in this.children ?
    //     this.children[k].find(ks) :
    //     S.Nothing;
};

// Trie a ~> String -> Bool
Trie.prototype.has = function has(k) {
    return !this.find(k).isNothing;
};

// Trie a ~> String -> Trie a
// Trie.prototype.subtrie = function subtrie(k) {};

// THIS will could be very useful for a tokenizing string reader
// Trie a ~> String -> Maybe [String, a, String]
// Trie.prototype.match = function match(k) {};

// Trie a ~> String -> [[String, a, String]]
// Trie.prototype.matches = function matches(k) {};

/* Single-value modification */

// Trie a ~> (String -> a -> Maybe a -> Maybe a) -> String -> a -> Trie a
// Trie.prototype.alterBy = function alterBy(f) {};

// Trie a ~> String -> a -> Trie a
Trie.prototype.insert = function insert(key, a) {
    const [k, ...ks] = key;
    if (k === undefined) {
        const n = Trie.of(a);
        n.children = this.children;
        return n;
    }
    const n = this.value.isNothing ? Trie.empty() : Trie.of(this.value.value);
    n.ks = [...this.ks, key];
    n.children = S.concat(
        this.children,
        {[k]: (k in this.children ?
               this.children[k] :
               Trie.empty()).insert(ks.join(''), a)});
    return n;
};

// Trie a ~> a -> Trie a
Trie.prototype.set = function set(a) {
    return this.insert('', a);
};

// Trie a ~> (a -> a) -> String -> Trie a
// Trie.prototype.adjust = function adjust(f, k) {};

// Trie a ~> String -> Trie a
Trie.prototype.delete = function delete_(k) {
    const o = this.toObject();
    delete o[k];
    return Trie.fromObject(o);
}

/* Combining tries */

// Trie a ~> (a -> a -> Maybe a) -> Trie a -> Trie a
// Trie.prototype.mergeBy = function mergeBy(f) {};

// Trie a ~> Trie a -> Trie a
// Trie.prototype.unionL = function unionL(o) {};

// Trie a ~> Trie a -> Trie a
Trie.prototype.unionR = Trie.prototype.concat;

/* Mapping functions */

// Trie a ~> (String -> a -> Maybe b) -> Trie b
// Trie.prototype.mapBy = function mapBy(f) {};

// Trie a ~> (a -> Maybe b) -> Trie b
// Trie.prototype.filterMap = function filterMap(f) {};

An in-progress port of Data.Trie