1

Is there a good way to compare 2 sets in ramda.js, whether one is another's super set / sub set?

for example,

const ss = new Set([1,2,3])

const s = new Set([1,2])

ss is a super set of s (s is subset).

Is there an easy way to achieve this in ramda.js?

Jared Smith
  • 19,721
  • 5
  • 45
  • 83
tim
  • 1,454
  • 1
  • 25
  • 45

3 Answers3

2

Yes. No ramda required.

const isSubsetOf = (s1, s2) => new Set([ ...s1, ...s2 ]).size === s1.size;

Returns true if s2 is a subset of s1. Adapted from this answer on a similar question about arrays.

Jared Smith
  • 19,721
  • 5
  • 45
  • 83
  • thanks for the answer. a big thumb up. I am still wondering whether there is a ramda.js way. – tim Sep 06 '19 at 02:48
  • @tim I mean you *could* do this with Ramda, but it isn't going to be any shorter, or more readable. It *might* be faster, and depending on the size of your sets it *might* matter, but that's a lot of maybes. – Jared Smith Sep 06 '19 at 02:50
  • 1
    @JaredSmith Depending on the size of the sets, this approach can be a whole lot *slower*. – Bergi Sep 06 '19 at 02:53
  • @tim I think the problem you'll find with using ramda for this task is that most (all?) of it's list and relation operations (e.g. union) expect Javascript arrays, they won't work with generic iterables like Sets. So you're going to have to convert them to arrays, feed them through ramda, then re-construct the sets. Not sure what you'd gain by doing so. – Jared Smith Sep 06 '19 at 02:59
  • 1
    @Bergi sure, it's piggishly wasteful, but it's also clear and concise. Wouldn't do for library code, but probably acceptable for a one-off. – Jared Smith Sep 06 '19 at 03:00
  • 2
    @tim: while it's perfectly possible to use Ramda functions to write this -- for instance, using, `all` as Bergi suggested (`(s) => (ss) => R.all (s => ss .has (s), [...s])`) -- such an approach probably offers nothing that vanilla JS doesn't offer just as cleanly: `(s) => (ss) => [...s] .every (s => ss .has (s))`. I'm one of the founders of Ramda and a big fan, but there seems no reason to use it here. – Scott Sauyet Sep 06 '19 at 11:28
2

Jared's answer is concise, but if the sets to compare were reasonably large, it is not an efficient algorithm.

Consider this short-circuiting program -

const isSubsetOf = (super, sub) => {
  for (const s of sub)
    if (!super.has(s))
      return false
  return true
}

In another Q&A, How to map/reduce/filter a Set in JavaScript?, we explore how to add functional methods to the Set.prototype. One in particular that would be useful to us, is Set.prototype.every -

Set.prototype.every = function every(f) {
  for (const v of this) if (!f(v)) return false
  return true
}

This would allow you to rewrite your program as -

const isSubsetOf = (super, sub) =>
  sub.every(s => super.has(s))

Modifying native prototypes is not recommended if you're writing shared software like a library, framework, or tool. However if this is your program and you don't expect it to become a dependency in someone else's project, there is nothing wrong with modifying any prototype (native or otherwise) to suit your needs.

If you cannot modify Set.prototype, a functional API is still possible -

const setEvery = (set, f) => {
  for (const v of this) if (!f(v)) return false
  return true
}

const isSubsetOf = (super, sub) =>
  setEvery(sub, s => super.has(s))
Mulan
  • 129,518
  • 31
  • 228
  • 259
2

First, let's see a non-Ramda solution, copied from MDN: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

function isSubsetOf(set, subset) {
  for (var elem of subset) {
    if (!set.has(elem)) return false;
  }
  return true;
}

Translating it into a point-free Ramda like a perfectionist:

// isSubsetOf :: Set -> Set -> Boolean
const isSubsetOf = 
  R.useWith
    (R.all)
    ([
      R.bind (Set.prototype.has),
      Array.from,
    ]);

const set1 = new Set([1, 2, 3]);
const set2 = new Set([1, 2]);
isSubsetOf (set1) (set2); // true

But I rather want a less point-free but more readable Ramda solution:

// isSubsetOf :: Set -> Set -> Boolean
const isSubsetOf = s1 => s2 =>
  R.all
    (x => s1.has(x))
    (Array.from(s2));

But actually a ES6 version is elegant enough:

// isSubsetOf :: Set -> Set -> Boolean
const isSubsetOf = s1 => s2 => 
  Array
    .from(s2)
    .every(x => s1.has(x));

IMO, logically, short vanilla javascript is elegant and readable enough especially for a small utility function like this one, unless you're so in love with FP and can't resist using FP library for it, or you're using sanctuary.js to achieve type-checking.

diccccn
  • 156
  • 1
  • 2
  • A possible optimisation: `if (set.size < subset.size) return false` – Bergi Sep 06 '19 at 12:24
  • 2
    The code copied from MDN is the only efficient algorithm in your answer. Implementations using `Array.from` make a complete copy of the input set. – Mulan Sep 06 '19 at 15:32
  • I think you name it wrongly, I think your solution to check is is super set, but you name it isSubset. – tim Sep 06 '19 at 19:19
  • @tim I didn't name it wrongly. If the first argument passing into the function is the "superset", you can make a partial function like `const isSubsetOfSet1 = isSubsetOf (set1)`, and do things like `filter (isSubsetOfSet1) ([set2, set3])` to filter set2 and set3 by checking if set1 is a superset of them. – diccccn Sep 07 '19 at 07:21