Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #29531

Re: passing a set of numbers to a function

Show all headers | View raw

Thomas 'PointedEars' Lahn wrote:
> Ben Bacarisse wrote:

>> Computer programs can implement infinite sets though only very few of
>> them (even fewer, compared to how many there are, than for finite sets).
> 
> AFAICS there is no intrinsic limit as to the implementation of infinite sets 
> (you just need a flexible enough data model to define them), however it 
> appears to be non-trivial to implement operations on some of them, for 
> example to determine if an item is an element of such a set.

There is a simple way to implement mathematical sets, finite or 
infinite using predicate functions.  But true sets from a mathematical 
perspective are very different from the sorts of Set types usually 
considered in software: collections to which items might be added or 
removed.

But for those interested in sets which have the normal set operations 
of `contains`, `union`, `intersection`, and `complement`, the 
following looks to be quite simple:

    const set = pred => ({
      contains: pred,
      union: set2 => set(val => pred(val) || set2.contains(val)),
      intersection: set2 => set(val => pred(val) && set2.contains(val)),
      complement: () => set(val => !pred(val))
    });

One could use this to create sets such as these:

    const fizz = set(n => n % 3 == 0);
    const buzz = set(n => n % 5 == 0);
    const fizzBuzz = fizz.intersection(buzz);
    const fizzOrBuzz = fizz.union(buzz);
    const notBuzz = buzz.complement();

These are somewhat oversimplified, as they should probably also test 
that the value supplied is a number, but the basic idea should be 
clear.

If you wanted to test them, this should make it clear how these sets 
work:

    const test = (s, nbrs) => nbrs.reduce((acc, val) => {
      acc[val] = s.contains(val);
      return acc;
    }, {})

    test(fizz, [6, 10, 14, 45]); 
    //=> {6: true, 10: false, 14: false, 45: true}

    test(buzz, [6, 10, 14, 45]); 
    //=> {6: false, 10: true, 14: false, 45: true}

    test(fizzBuzz, [6, 10, 14, 45]);
    //=> {6: false, 10: false, 14: false, 45: true}

    test(fizzOrBuzz, [6, 10, 14, 45]); 
    //=> {6: true, 10: true, 14: false, 45: true}

    test(notBuzz, [6, 10, 14, 45]);
    //=> {6: true, 10: false, 14: true, 45: false}

But, for one trying to use a set as a Collection, these are missing 
several important features.  Obviously there is no way to add or 
remove members.  There is also no generic way to iterate, although 
obviously one could create iterators to match specific Sets.  So, 
while this is reasonably close to mathematical sets, they are not 
really close to what are usually considered sets in software.

We should also note that this misses at least one important notion 
from mathematics as well.  I'm fairly certain that there is no way to 
write a `subset` function.  I haven't proven this, but I'm guessing 
that the sort of logic that shows that the Halting Problem is 
insoluble or the logic that proves Rice's Theorem would also 
demonstrate that this can't be done.


  -- Scott

Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

passing a set of numbers to a function Matheus Suffi <matheus.suffi40@gmail.com> - 2016-01-25 04:45 -0800
  Re: passing a set of numbers to a function Aleksandro <aleksandro@gmx.com> - 2016-01-25 10:51 -0300
  Re: passing a set of numbers to a function Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-29 03:57 +0100
    Re: passing a set of numbers to a function Joao Rodrigues <groups_jr-1@yahoo.com.br> - 2016-01-28 23:19 -0800
      Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-29 10:09 +0000
        Re: passing a set of numbers to a function John Harris <niam@jghnorth.org.uk.invalid> - 2016-01-29 10:20 +0000
          Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-29 12:23 +0000
            Re: passing a set of numbers to a function John Harris <niam@jghnorth.org.uk.invalid> - 2016-01-29 14:50 +0000
              Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-29 16:11 +0000
                Re: passing a set of numbers to a function John Harris <niam@jghnorth.org.uk.invalid> - 2016-01-30 10:10 +0000
          Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-29 08:35 -0800
            Re: passing a set of numbers to a function John Harris <niam@jghnorth.org.uk.invalid> - 2016-01-30 10:34 +0000
              Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-30 18:53 -0800
                Re: passing a set of numbers to a function John Harris <niam@jghnorth.org.uk.invalid> - 2016-01-31 14:50 +0000
                Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-31 09:56 -0800
                Re: passing a set of numbers to a function John Harris <niam@jghnorth.org.uk.invalid> - 2016-02-01 11:02 +0000
                Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-02-01 18:10 -0800
        Re: passing a set of numbers to a function Gene Wirchenko <genew@telus.net> - 2016-01-29 09:38 -0800
          Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-29 20:17 +0000
        Re: passing a set of numbers to a function Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-29 20:08 +0100
    Re: passing a set of numbers to a function Aleksandro <aleksandro@gmx.com> - 2016-01-29 10:32 -0300
      Re: passing a set of numbers to a function "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2016-01-29 14:53 +0100
        Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-29 06:26 -0800
    Re: passing a set of numbers to a function John Harris <niam@jghnorth.org.uk.invalid> - 2016-01-29 14:19 +0000
      Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-29 08:38 -0800
        Re: passing a set of numbers to a function Aleksandro <aleksandro@gmx.com> - 2016-01-29 13:54 -0300
          Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-29 10:11 -0800
            Re: passing a set of numbers to a function Aleksandro <aleksandro@gmx.com> - 2016-01-29 15:38 -0300
            Re: passing a set of numbers to a function Anders Wegge Keller <wegge@geostat.dk> - 2016-01-29 20:13 +0100
              Re: passing a set of numbers to a function Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-29 20:46 +0100
                Re: passing a set of numbers to a function Aleksandro <aleksandro@gmx.com> - 2016-01-29 16:59 -0300
          Re: passing a set of numbers to a function Erwin Moller <erwinmollerusenet@xs4all.nl> - 2016-02-12 12:03 +0100
  Re: passing a set of numbers to a function Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-02 11:18 +0100
    Re: passing a set of numbers to a function Aleksandro <aleksandro@gmx.com> - 2016-02-02 12:31 -0300
    Re: passing a set of numbers to a function John Harris <niam@jghnorth.org.uk.invalid> - 2016-02-04 10:42 +0000
      Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-04 15:38 +0000
        Re: passing a set of numbers to a function Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-04 17:33 +0100
          Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-02-04 16:19 -0800
            Re: passing a set of numbers to a function Stefan Weiss <krewecherl@gmail.com> - 2016-02-05 14:06 +0100
              Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-02-05 05:45 -0800
                Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-05 14:34 +0000
                Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-05 15:42 +0000
                Re: passing a set of numbers to a function Stefan Weiss <krewecherl@gmail.com> - 2016-02-05 16:04 +0100
                Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-02-05 10:48 -0800
                Re: passing a set of numbers to a function Stefan Weiss <krewecherl@gmail.com> - 2016-02-06 04:50 +0100
                Re: passing a set of numbers to a function "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-02-06 10:05 -0800
                Re: passing a set of numbers to a function Stefan Weiss <krewecherl@gmail.com> - 2016-02-06 23:30 +0100
                Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-02-06 17:32 -0800
              Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-05 14:13 +0000
                Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-05 17:15 +0000
            Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-02-05 05:19 -0800
              Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-05 13:43 +0000
                Re: passing a set of numbers to a function Scott Sauyet <scott.sauyet@gmail.com> - 2016-02-05 06:08 -0800
        Re: passing a set of numbers to a function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-04 20:25 +0000
        Re: passing a set of numbers to a function John Harris <niam@jghnorth.org.uk.invalid> - 2016-02-05 10:51 +0000

csiph-web