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

Groups > comp.lang.javascript > #29506

Re: passing a set of numbers to a function

Show all headers | View raw

John Harris wrote:
> Scott Sauyet wrote:

>> And if that is unclear, look at the definitions of Bags/Multisets, which
>> intentionally distinguish themselves from Sets precisely on the ability
>> to contain duplicates.
> 
> If you take your Multisets and ignore the multiplicities then you have
> something that has equals and IsMember and obeys the set axioms. It
> waddles like a set and it quacks like a set so it is therefore (an
> implementation of) a set.

I'm trying hard to avoid being too pedantic.  This group already has at
least one too many super-pedants.

So, I certainly do understand what you're saying.  One can logically
project a Multiset and get a Set.

But you seem to want to have it both ways, claiming that something is
both a Multiset and a Set, and that I can't buy.  (At least not in the
case of a Multiset with an element of multiplicity greater than 1.)

You say that if you "ignore the multiplicities...", then it's set-like.
Sure.  And if I ignore the composites, the integers act just like the
set of primes.


> As for implementations in programs, when you choose a data structure
> to represent small finite sets then it's the application requirements
> that bias your choice. If lightning fast Union is required but other
> standard set operations are much less important then you would choose
> linked lists with Union as concatenation. Then IsMember is slow and
> Intersection is horrifically slow, and members can occur twice. If you
> want very fast IsMember you would choose sorted arrays, with IsMember
> using a binary search. Then it becomes important to ensure that no
> member occurs many times; Union and Intersection are coded
> accordingly.


I think the important point is here.  The discussion about the
mathematical structures offends me, as you seem to conflate the two
notions inappropriately.  But you are certainly correct that one can
implement Sets in a number of ways in software, including with 
techniques that internally include duplicates.  In such techniques,
not only is intersection difficult, though: iteration can also be
a real challenge.

In the end, in software both the API and the performance 
characteristics can matter a lot.  But for defining whether an
implementation actually meets a spec, it's only the API.  And if
multiplicities leak into the API, then it's not a set:

   var s = new MySetType(['a', 'b', 'a']);
   forEach(s, log);

If this code (for some fairly obvious functions, `forEach` and `log`) 
logs two output statements, 'a', and 'b', in some order, then 
`MySetType` might well be a Set implementation.  But if it logs three 
output statements, two 'a's and a 'b', in any order, then it, to my 
mind, does not qualify as an implementation of the mathematical notion 
of a Set.  I'm sure I could write some formal rules to codify this if 
I felt really motivated, but this should be clear enough.


This also helps respond to your answer to Ben 
(in <ql2pabpigiko0q6o2bafb1blb2hea5raid@4ax.com>):

| With the conventional meaning, the cardinality being 1 means that
| there is a bijection between {x} and the set {{}}. Being a bijection
| relies on membership, not at all on multiplicity. 

If you iterate, or list the members of your MultiSet, and the multiply-
occuring ones appear in the list more than once, you have an issue
trying to get a bijection with the appropriate set: 

Again, with the Multiset {a, b, a}; by definition, this has cardinality
of 3, but any attempted bijection with {0, 1, 2} will fail, which will
show that it is not a set.  Now you could claim that it has a
cardinality of 2, and get proper bijections, but then you're back in
the world of plain Sets and your iterator must only yield two elements.

So I think we may just be arguing about terminology.  But if you do
want to claim that you should be able to iterate a Set and see the
underlying implementation's multiplicities repeating themselves, then
our disagreement is fundamental.

  -- 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