Path: csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.lang.javascript Subject: Re: passing a set of numbers to a function Date: Fri, 05 Feb 2016 17:15:28 +0000 Organization: A noiseless patient Spider Lines: 86 Message-ID: <87bn7vkrin.fsf@bsb.me.uk> References: <19679ed0-c594-4f7e-817c-a72bd5c10411@googlegroups.com> <22041181.SJtjrm8m6U@PointedEars.de> <87r3gso59h.fsf@bsb.me.uk> <1603158.xI32ru06Pi@PointedEars.de> <58b65993-5943-4f8e-a4e2-9e97bb1feea3@googlegroups.com> <87zivfkzyi.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="25327"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19ThkCDuDHpOdZtsY6BRgd3MmmYUb25fLk=" Cancel-Lock: sha1:uyKDnCcAkGlTyeL/o8p9C/0Le98= sha1:LT4sFUdlhr0Ao9SiGkmFNknFhOI= X-BSB-Auth: 1.8427eece018cfdb62a78.20160205171528GMT.87bn7vkrin.fsf@bsb.me.uk Xref: csiph.com comp.lang.javascript:29547 Ben Bacarisse writes: > Stefan Weiss writes: > >> On 02/05/2016 01:19, Scott Sauyet wrote: >>> There is a simple way to implement mathematical sets, finite or >>> infinite using predicate functions. [...] >>> >>> 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(); >> >> A very nice example. >> >> [snip tests] >> >>> 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. >> >> Why? Wouldn't "subset" just be one more predicate to be combined with >> the set's predicate? > > If S1 \subset S2 and S2 \subset S1 then S1 = S2. Hence a correct subset > predicate could determines if two functions compute the same value in > all cases. > > Similarly, you can't implement an isEmpty predicate either and, as Scott > suggested, I think some version of Rice's theorem will come into play so > that no "interesting" property of sets of sets will be decidable. > > (I'm not knocking the method. This is what I had in mind when I talked > about implementing infinite sets because membership was, at that point, > the only operation that was wanted.) > >> "intersection" already does that. The same would go >> for adding or removing individual members or (sub)sets, using "union" >> and "intersection", respectively. >> >> As for iterators, sets don't have an inherent order, so any kind of >> ordered iteration would be an extension to the concept. The ability to >> produce members, in any order, is also not a required property of a >> set. > > That's a hot topic! See the well-ordering theorem of ZFC. Mind you, > this is obviously not ZFC since it can express Russell's paradox: > > function russell(m, s) { return s.contains(m); } That's a terrible name! It has very little to do with end result and it's just as artefact left over from some editing. If it's named at all it should be function russell(s) { return !s.contains(s); } (and R is then just set(russell)) but it's probably simpler just to write const R = set(x => ! x.contains(x)); R.contains(R); -- Ben.