Functional data structures in JavaScript with Mori

mori.markdown

Functional data structures in JavaScript with Mori

http://swannodette.github.io/mori/

the basic immutable structure: list

var l0 = mori.list(3, 4, 5);

var l1 = mori.cons(2, l0);

var l2 = mori.cons(1, l1);

ASCII art

(1  2  3  4  5);
 ^  ^  ^
 |  |  \ l0
 |  |
 |  \ l1
 |
 \ l2

Mori data structures are immutable

var mori = require('mori');

var v0 = mori.vector(1, 2, 3);
var v1 = mori.conj(v1, 4);

assert( String(v1) === '[1 2 3 4]' );
assert( String(v0) === '[1 2 3]' );

Data structures available

• list
• vector
• range
• hash_map
• array_map
• sorted_map
• sorted_map_by
• set
• sorted_set
• sorted_set_by

hash_map

var mori = require('mori');

var a = { foo: 1 };
var b = { foo: 2 };

var map = mori.hash_map(a, 'first', b, 'second');

assert( mori.get(map, b) === 'second' );

hash_map

var m0 = mori.hash_map();
var m1 = mori.assoc (m0, 'foo', 1);
var m2 = mori.assoc (m1, 'bar', 2, 'nao', 3);
var m3 = mori.dissoc(m2, 'foo');

assert(mori.get(m2, 'foo') === 1);
assert(mori.get(m2, 'bar') === 2);
assert(mori.get(m3, 'foo') === null);

sorted_set_by

var s0 = mori.sorted_set_by(function(a, b) {
    return b - a;
});

var s1 = mori.into(s, [1, 2, 3, 4, 5]);

String(s1);
//> '#{5 4 3 2 1}'

Calendar

function Calendar(appts) {
    appts = appts || mori.sorted_set_by(compare_appts);
    var cal = {};

    cal.add = function(appt) {
        var with_appt = mori.conj(appts, appt);
        return Calendar(with_appt);
    };

    cal.upcoming = function(start, n) {
        var futureAppts = mori.filter(function(a) {
            return a.date >= start;
        }, appts);
        return mori.take(n, futureAppts);
    };

    return cal;
}

Calendar

function Calendar(appts) {
    appts = appts || mori.sorted_set_by(compare_appts);
    /* ... */
}

function compare_appts(a, b) {
    if (a.date !== b.date) {
        return a.date - b.date;
    }
    else {
        return (a.title) .localeCompare (b.title);
    }
}

Calendar usage

var my_cal = Calendar().add({
    title: "Portland JavaScript Admirers' Monthly Meeting",
    date:  Date.parse("2013-10-23T19:00-0700")
}).add({
    title: "North Portland Coders Night",
    date:  Date.parse("2013-10-28T18:30-0700")
}).add({
    title: "BarCamp Portland 8 Volunteer Meetup!",
    date:  Date.parse("2013-11-04T18:30-0700")
}).add({
    title: "Cascadia Ruby 2013",
    date:  Date.parse("2013-10-21T08:00-0700")
});

Calendar usage

var now = new Date();
var next_appts = my_cal.upcoming(now, 2);

mori.map(function(a) { return a.title; }, next_appts);
//> ("North Portland Coders Night" "BarCamp Portland 8 Volunteer Meetup!")

undo!

function Calendar(appts, prev_cal) {
    /* ... */

    cal.add = function(appt) {
        var with_appt = mori.conj(appts, appt);
        return Calendar(with_appt, cal);
    };

    cal.undo = function() {
        return prev_cal || Calendar();
    };

    /* ... */
}

Apples to apples

function compact(coll) {
    var no_nulls = mori.filter(function(elem) {
        return elem !== null;
    }, coll);
    return mori.into(mori.vector(), no_nulls);
}

Apples to apples

function compact(coll) {
    var no_nulls = mori.filter(function(elem) {
        return elem !== null;
    }, coll);
    return mori.into( /**/ mori.empty(coll) /**/, no_nulls);
}

Mori pairs well with Bacon

https://github.com/baconjs/bacon.js

Performance

constructor	insert time	lookup time
list	1	n
array_map	1	n
vector	log_32 n	log_32 n
set	log_32 n	log_32 n
hash_map	log_32 n	log_32 n
sorted_map	log_2 n	log_2 n
sorted_map_by	log_2 n	log_2 n
sorted_set	log_2 n	log_2 n
sorted_set_by	log_2 n	log_2 n

Laziness

var non_neg_ints = mori.range();
var nats         = mori.drop(1, non_neg_ints);

var log_2    = function(n) { return Math.log(n) / Math.LN2; };
var is_pow_2 = function(n) { return log_2(n) % 1 === 0; };

var pows_2   = mori.filter(is_pow_2, nats);

mori.take(10, pows_2)
//> (1 2 4 8 16 32 64 128 256 512)

Fibonacci

function fibs() {
    var pairs = mori.iterate(function(pair) {
        var x = pair[0], y = pair[1];
        return [y, x + y];
    }, [0, 1]);
    return mori.map(mori.first, pairs);
}

mori.take(10, fibs())
//> (0 1 1 2 3 5 8 13 21 34)

Fibonacci (mind-bending version)

var fibs = mori.cons(0, mori.cons(1, mori.map(
    function(x, y) {
        return x + y;
    },
    mori.mapcat(function() { return fibs;               }, mori.list(0)),
    mori.mapcat(function() { return mori.drop(1, fibs); }, mori.list(0))
)));