merge-monoids.js

// A sketch for building up mergeable monoids (mms) from component mms.
// Status: A quick sketch of low quality in terminology, code and presentation...

// A *mergeable monoid* (*mm*) is a regular monoid (a carrier set S, an associative
// concatenation function + (S, S) -> S, and a neutral element e:S) together with
// a *conflict detection function* cdf (S, S) -> bool that returns true if
// s1 + s2 == s2 + s1 (i.e. if there is no merge conflict), false otherwise.
const canonic_cdf = (concat) => (s1, s2) => (concat(s1, s2) === concat(s2, s1));

// The cdf can be more efficient than actually performing that test, e.g. for a
// commutative monoid, `() => true` can be used.
//
// When representing an atomic mm (an mm that is directly defined rather than
// composed from further mms), we don't explicitly give the underlying set, since
// js is dynamically typed.
// +, e, and cdf are given as an object, e.g. for the string concatenation mm:

const string_concat_mm = {
  tag: "atomic", // the wrapper object indicates that this is an atomic mm
  def: {
    concat: (s1, s2) => s1.concat(s2),
    neutral: "",
    cdf: canonic_cdf((s1, s2) => s1.concat(s2)),
  },
};
const int_add_mm = {
  tag: "atomic",
  def: {
    concat: (n, m) => n + m,
    neutral: 0,
    cdf: () => true,
  },
};
// A "production-ready" version of this should be compatible with the fantasyland spec:
// https://github.com/fantasyland/fantasy-land#monoid

// It might be worth exploring cdfs that are merely conservative approimations
// (might return false even if there is no merge conflict) for efficiency
// reasons, for example `(_, s1, s2) => s1 === s2`.
// In such a framework, the representation of an mm should include a
// boolean whether it is exact or not, the flag of a composite mm would be true
// iff all child flags were true.

// Back on track: Besides atomic mms, we want to be able to compose mms:
// {
//   tag: "composite",
//   def: ...,
// }
//
// The def value can be an obejct whose values are mms, or an array whose values are mms.
const example_composite_mm = {
  tag: "composite",
  def: {
    "some_counter": int_add_mm,
    "other_thing": {
      tag: "composite",
      def: [string_concat_mm, int_add_mm],
    }
  }
};

// A few concrete values from this monoid:

const example_a = {
  "some_counter": 3,
  "other_thing": ["foo", 42],
};
const example_b = {
  "some_counter": 4,
  "other_thing": ["bar", 0],
};
const example_c = {
  "some_counter": 1,
  // omitting the other_thing entry works like implictly giving the neutral
  // element of the other_thing. Note that this means that there are multiple
  // ways of representing the same element of the monoid. In particular, there
  // are multiple neutral elements (for this monoid, e.g. both `{}` and `{some_counter: 0}`)
  // would be neutral elements. This is kinda funky since neutral elements are
  // supposed to be unique
};
const expected_ab = {
  "some_counter": 7,
  "other_thing": ["foobar", 42],
};
const expected_ba = {
  "some_counter": 7,
  "other_thing": ["barfoo", 42],
};
const expected_ac = {
  "some_counter": 4,
  "other_thing": ["foo", 42],
}

// Concatenation and neutral elements work element-wise. We can give general
// functions that derive +, e, and cdf from such a (nested) mm descriptor.

function mm_to_concat(mm) {
  if (mm.tag == "atomic") {
    return mm.def.concat;
  } else if (Array.isArray(mm.def)) {
    return (s1, s2) => {
      let ret = [];

      for (var i = 0; i < mm.def.length; i++) {
        ret.push(mm_to_concat(mm.def[i])(s1[i], s2[i]));
      }

      return ret;
    };
  } else {
    return (s1, s2) => {
      let ret = {};

      for (let [key, value] of Object.entries(mm.def)) {
        if (mm.def.hasOwnProperty(key)) {
          const concat = mm_to_concat(value);
          if (s1.hasOwnProperty(key)) {
            if (s2.hasOwnProperty(key)) {
              ret[key] = concat(s1[key], s2[key]);
            } else {
              ret[key] = s1[key]; // absence in s2 works like neutral element
            }
          } else {
            if (s2.hasOwnProperty(key)) {
              ret[key] = s2[key];
            } else {
              // no-op, neither input has the key, so works like neutral element
            }
          }
        }
      }

      return ret;
    };
  }
};

function mm_to_e(mm) {
  if (mm.tag == "atomic") {
    return mm.def.neutral;
  } else if (Array.isArray(mm.def)) {
    return mm.def.map((def) => mm_to_e(def));
  } else {
    return {};
  }
};

// Stuff we can now do:
const example_concat = mm_to_concat(example_composite_mm);
const example_e = mm_to_e(example_composite_mm);

const deep_eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
console.log(deep_eq(example_concat(example_a, example_b), expected_ab));
console.log(deep_eq(example_concat(example_b, example_a), expected_ba));
console.log(deep_eq(example_concat(example_a, example_c), expected_ac));

// Exercise to the reader: define mm_to_cdf
//
// Further stuff: define merge prodcedures as async functions, extend the
// description of atomic mms to include merge procedures, then write a function that
// turns an mm description into a (potentially composite) merge procedure that
// invokes the contained merge procedures, but only where the cdf reports a conflict.