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

Groups > comp.lang.javascript > #29507

Re: passing a set of numbers to a function

Show all headers | View raw

On Sat, 30 Jan 2016 18:53:10 -0800 (PST), Scott Sauyet
<scott.sauyet@gmail.com> wrote:

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

Be careful. You're in danger of saying ECMAScript can't do integer
arithmetic because all numbers are floating point numbers. Do you
really say 3.0 can't be used as both a floating point number and an
integer?


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

If you look at the Wikipedia article on Multisets you'll see it starts
by saying members of a set can only occur once, then later on quotes a
world class mathematician as saying "The notion of a set takes no
account of multiple occurrence of any one of its members, and yet it
is just this kind of information which is frequently of importance."
  <https://en.wikipedia.org/wiki/Multiset#Applications>


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

It's an attempt at a set, but the coding bugs are so horrible that the
program can't be used until they are cured. Regardless of whether you
allow or disallow multiple occurrences there is code that must be got
right, else disaster.

The important thing when implementing sets is not to be afraid of
multiple occurrences. They are mathematically legitimate, but usually
cause more coding problems than they are worth.


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

Oh dear, a novel :-)

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

Who said there can be only one kind of iterator? Who says you can't
have an iterate_first_occurrences_only iterator? It's easy enough to
define; if set contents are always sorted then it's easy enough to
implement.


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

You are using a different definition of "cardinality". Peculiar
results are to be expected.


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

Exactly. They may be Multisets, but you can use them as sets provided
you write correct code.


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

That's the exact opposite of what I'm saying. Remember, this subthread
started with the question
  How can you tell? 
(That Sets don't contain duplicates)

  John

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