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 14:13:09 +0000 Organization: A noiseless patient Spider Lines: 74 Message-ID: <87zivfkzyi.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> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="15626"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19jYTgsB5Ske4ZXcoTN+KLttU7/6OypJ7g=" Cancel-Lock: sha1:TgwtJeLCUdK4aFJiG3arU65XY9Q= sha1:OYQJ9NcfaxJv9rojo8YoqTOIhWI= X-BSB-Auth: 1.2ca9566b5cca2ed75470.20160205141309GMT.87zivfkzyi.fsf@bsb.me.uk Xref: csiph.com comp.lang.javascript:29540 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); } const R = set(x => !russell(x, x)); R.contains(R); -- Ben.