Re: Set-returning .keys
Darren Duncan schreef: TSa: And I still think that it is a good idea to name the set operations after their equivalent boolean connectives: (|) union () intersection (^) symmetric difference Well, and to make them Bag operations to start with. To start off with, I agree with your comment about making Set the main type and making Bag an extension built upon that, as complex is built upon num, etc. I don't think that will work out. Modification of a Set is more complex than modification of a Bag, so in that sense the Bag is the main type. This may be a non-issue from a user's viewpoint, but as a user, I want set operations that have sets as input to return sets as output by default. Eg, unioning 2 Set that have common values should return a Set. Or base it on what the receiving end wants. I see the matter as being similar to Int vs Num. Any operation whose operands are Ints should return Ints wherever it is conceivable to do so. In particular, this means that dividing an Int by an Int should return an Int. Int three = 3 ; Int four = 4 ; Num n1 = three / four ; Num n2 = 3 / 4 ; (Is Int three the same as my Int three? I hope so.) -- Groet, Ruud
Re: Set-returning .keys
Ruud H.G. van Tol writes: Darren Duncan schreef: TSa: set operations ... make them Bag operations to start with. I agree with ... making Set the main type and making Bag an extension built upon that, as complex is built upon num, etc. I don't think that will work out. Modification of a Set is more complex than modification of a Bag, so in that sense the Bag is the main type. Is this still the Perl 6 _Language_ group? The one where we consider what Perl 6 will do, and leave the implementation details to others? Smylers
Re: Set-returning .keys
Smylers schreef: Ruud H.G. van Tol: Darren Duncan: TSa: set operations ... make them Bag operations to start with. I agree with ... making Set the main type and making Bag an extension built upon that, as complex is built upon num, etc. I don't think that will work out. Modification of a Set is more complex than modification of a Bag, so in that sense the Bag is the main type. Is this still the Perl 6 _Language_ group? The one where we consider what Perl 6 will do, and leave the implementation details to others? I don't consider much in this thread implementation oriented. In the part that you quote, I mentioned that putting a hierarchical order on Set vs. Bag has problems, because that order only applies to one side of them. The order was used for fall-back, to which I mentioned a context driven approach (like wantarray). -- Affijn, Ruud Gewoon is een tijger.
Re: Set-returning .keys
At 10:54 AM +0100 11/28/06, Ruud H.G. van Tol wrote: To start off with, I agree with your comment about making Set the main type and making Bag an extension built upon that, as complex is built upon num, etc. I don't think that will work out. Modification of a Set is more complex than modification of a Bag, so in that sense the Bag is the main type. On the contrary, I would say that a Bag is more complicated than a Set, both conceptually, and implementation-wise for many types of implementations. For conceptual, with a Set, you just know that a particular element either does or does not exist in it. With a Bag, you additionally have a count of how many times that element exists (with a more practical Hash-like implementation), or you have an actual multiplicity of instances (with a less practical Array-like implementation), which is more information and more complicated. Look at these implemented in terms of a Hash-like collection, for example. A Set only has to maintain the list of keys, while the Bag also has to maintain the associated count values for each. When Hash values can be safely never defined, or ignored or dropped at any given time, as with the Hash-like Set, there is less work to do than if any of them are accounted for. What I have said above is the same message regardless of whether Set and/or Bag are immutable or mutable, though I assume that as Perl 6 already has Set being immutable, then if Bag were added, it would be too. -- Darren Duncan
Re: Set-returning .keys (was Re: Smart Matching clarification)
HaloO, Darren Duncan wrote: This may be a non-issue from a user's viewpoint, but as a user, I want set operations that have sets as input to return sets as output by default. Eg, unioning 2 Set that have common values should return a Set. First of all the operations could be overloaded. Secondly the bag operations are defined in terms of min and max and therefore result in Sets remaining Sets at least in the sense of a Bag with all element multiplicities being 1. Moreover, since set operations would be a lot more common in practice than bag operations, the set operations should be the most terse, if they both aren't equally terse. I think the operators are the same. And with Seq a subtype of Bag they are applicable to Seqs as well. Some operations like (+) however make no sense for Sets and so they return a Bag. That is similar to using Bool values as arguments to numeric operations: True + True == 2. I see the matter as being similar to Int vs Num. Any operation whose operands are Ints should return Ints wherever it is conceivable to do so. In particular, this means that dividing an Int by an Int should return an Int. As a kind of compromise an Int division could return a doubled value with but: 5 / 4 == 1 but 1.25. (Also, the modulus should be undefined for 2 Num.) This could be achieved by introducing the modulus on the Int level. But I think that modulus can be easily generalized to Num. E.g. 3.2 % 2.4 == 0.8. Handling negative divisors is more of an issue. With the Euclidean definition of modulus a negative sign should not propagate into the result. E.g. 8 % -3 == 8 % 3 == 2. Only promote an Int to a Num if one or more other operands are already Num, even if the value of that Num is a whole number. I'm not sure that this is the intent of the current spec. I personally value adherence to the subtyping of Int and Num higher than keeping a pure Int subsystem. Regards, TSa. --
beg for Bag
HaloO, as a spin-off of the 'Set-returning .keys (was Re: Smart Matching clarification)' thread I want to propose the addition of a Bag type that completes the set of immutable types. It shall have the following properties. 1) It is a multiset generalization of Set 2) It is a supertype of Set and Seq (a Set can of course be build from a Seq). That is 'Set does Bag' and 'Seq does Bag'. Note that a Seq is a ready-made Bag and if it happens to have no duplicates it behaves like a Set. 3) It has set operations as generalizations of the Set operations 4) It provides some Bag specific ops like (+) that return a Bag even when called with Sets 5) It provides the iteration interface (which in turn is applicable to the subtypes Set and Seq, of course) 6) %hash.values returns a Bag 7) %hash.keys returns a Set The wording in section 'Immutable Types' in S06 concerning Set as Unordered Seqs that allow no duplicates is a bit misleading because it hints as Set being a subtype of Seq. The Mapping could be explained as Set of Pair. The Bag type could be implemented in a module but then we need a way to do supertyping. The added Bag type would need to add a multiplicity accessor that returns 1 to the Set implementation and add lazy multiplicity counting to Seq. And I don't know how Hash::values would be augmented to return a Bag. This Bag return type would guarantee %h1.values === %h2.values to yield true when the two hashes happen to return their values in different orders. Comments? --
Re: beg for Bag
TSa writes: I want to propose the addition of a Bag type Different from the CBag that's already mentioned in Synopsis 3? Smylers
Re: beg for Bag
At 7:08 PM + 11/28/06, Smylers wrote: TSa writes: I want to propose the addition of a Bag type Different from the CBag that's already mentioned in Synopsis 3? Smylers TSa wasn't the first person to ask for an explicit Bag type. I did too, a few weeks ago. And one reason for that was exactly what you mention. Various other parts of the Synopsis documents mention Bag in examples and such, but the list of built-in types in Synopsis 6 does not include it. In my mind, unless Bag appears in the Synopsis 6 list, its references elsewhere count as nothing more than an example stand-in for some arbitrary user-defined type. -- Darren Duncan
[svn:perl6-synopsis] r13483 - doc/trunk/design/syn
Author: larry Date: Tue Nov 28 17:27:59 2006 New Revision: 13483 Modified: doc/trunk/design/syn/S06.pod Log: Distinguished Set and Bag values from KeySet and KeyBag containers. Modified: doc/trunk/design/syn/S06.pod == --- doc/trunk/design/syn/S06.pod(original) +++ doc/trunk/design/syn/S06.podTue Nov 28 17:27:59 2006 @@ -13,9 +13,9 @@ Maintainer: Larry Wall [EMAIL PROTECTED] Date: 21 Mar 2003 - Last Modified: 31 Oct 2006 + Last Modified: 28 Nov 2006 Number: 6 - Version: 60 + Version: 62 This document summarizes Apocalypse 6, which covers subroutines and the @@ -1365,8 +1365,9 @@ Block Executable objects that have lexical scopes ListLazy Perl list (composed of Seq and Range parts) Seq Completely evaluated (hence immutable) sequence -Range Incrementally generated (hence lazy) sequence -Set Unordered Seqs that allow no duplicates +Range A pair of Ordered endpoints; gens lazy Seq in list context +Set Unordered Seq that allows no duplicates +Bag Unordered Seq that allows duplicates JunctionSets with additional behaviours PairSeq of two elements that serves as a one-element Mapping Mapping Pairs with no duplicate keys @@ -1379,9 +1380,12 @@ Objects with these types have distinct C.WHICH values that do not change even if the object's contents change. +Scalar Perl scalar Array Perl array HashPerl hash -Scalar Perl scalar +KeyHash Perl hash that autodeletes values matching default +KeySet KeyHash of Bool (does Set in list/array context) +KeyBag KeyHash of UInt (does Bag in list/array context) Buf Perl buffer (a stringish array of memory locations) IO Perl filehandle Routine Base class for all wrappable executable objects @@ -1398,6 +1402,38 @@ Object Perl 6 object Grammar Perl 6 pattern matching namespace +A CKeyHash differs from a normal CHash in how it handles default +values. If the value of a CKeyHash element is set to the default +value for the CKeyHash, the element is deleted. If undeclared, +the default default for a CKeyHash is 0 for numeric types, CFalse +for boolean types, and the null string for string and buffer types. +A CKeyHash of a CObject type defaults to the undefined prototype +for that type. More generally, the default default is whatever defined +value an Cundef would convert to for that value type. A CKeyHash +of CScalar deletes elements that go to either 0 or the null string. +A CKeyHash also autodeletes keys for normal undef values (that is, +those undefined values that do not contain an unthrown expections). + +A CKeySet is a CKeyHash of booleans with a default of CFalse. +If you you use the CHash interface and increment an element of a +CKeySet its value becomes true (creating the element if it doesn't +exist already). If you decrement the element it becomes false and +is automatically deleted. When not used as a CHash (that is, +when used as an CArray or list or CSet object) a CKeySet +behaves as a CSet of its keys. (Since the only possible value of +a CKeySet is the CTrue value, it need not be represented in +the actual implementation with any bits at all.) + +A CKeyBag is a CKeyHash of CUInt with default of 0. If you +you use the CHash interface and increment an element of a CKeyBag +its value is increased by one (creating the element if it doesn't exist +already). If you decrement the element the value is decreased by one; +if the value goes to 0 the element is automatically deleted. When not +used as a CHash (that is, when used as an CArray or list or CBag +object) a CKeyBag behaves as a CBag of its keys, with each key +replicated the number of times specified by its corresponding value. +(Use C.kv or C.pairs to suppress this behavior in list context.) + =head2 Value types Explicit types are optional. Perl variables have two associated types:
Re: beg for Bag
TSa wrote: 1) It is a multiset generalization of Set 2) It is a supertype of Set and Seq (a Set can of course be build from a Seq). That is 'Set does Bag' and 'Seq does Bag'. Note that a Seq is a ready-made Bag and if it happens to have no duplicates it behaves like a Set. 3) It has set operations as generalizations of the Set operations Note that this would mean that Seq would also have set operations. 4) It provides some Bag specific ops like (+) that return a Bag even when called with Sets or Seqs. -- Jonathan Dataweaver Lang
[svn:perl6-synopsis] r13484 - doc/trunk/design/syn
Author: larry Date: Tue Nov 28 19:22:48 2006 New Revision: 13484 Modified: doc/trunk/design/syn/S06.pod Log: typo Modified: doc/trunk/design/syn/S06.pod == --- doc/trunk/design/syn/S06.pod(original) +++ doc/trunk/design/syn/S06.podTue Nov 28 19:22:48 2006 @@ -1412,7 +1412,7 @@ value an Cundef would convert to for that value type. A CKeyHash of CScalar deletes elements that go to either 0 or the null string. A CKeyHash also autodeletes keys for normal undef values (that is, -those undefined values that do not contain an unthrown expections). +those undefined values that do not contain an unthrown expection). A CKeySet is a CKeyHash of booleans with a default of CFalse. If you you use the CHash interface and increment an element of a
Re: [svn:perl6-synopsis] r13483 - doc/trunk/design/syn
At 5:28 PM -0800 11/28/06, [EMAIL PROTECTED] wrote: Author: larry Date: Tue Nov 28 17:27:59 2006 New Revision: 13483 Modified: doc/trunk/design/syn/S06.pod Log: Distinguished Set and Bag values from KeySet and KeyBag containers. snip Ah, thank you. A nice clean-looking solution which accounts for many aspects of the relevant problem space. -- Darren Duncan
