Re: [perl] The Sort Problem
Joe Gottman wrote in perl.perl6.language : This is unrelated to the problem you mentioned, but there is another annoying problem with sort as it is currently defined. If you have an @array and you want to replace it with the sorted version, you have to type @array = sort @array; Besides being long-winded, this causes Perl to make an unnecessary copy of the array. It would be nice calling if sort (or reverse, or other similar functions) in void context resulted in in-place modification of the array that was input. I'd rather not change the behaviour of sort (or other built-ins that may or may not operate in place) depending on the calling context. What to do, for example, when Csort is the last statement of a sub? Besides this, a construction like @x = sort @x could be detected by a suitable optimizer and turned to (internally) an in-place sort. (It appears that Dave Mitchell is working on such an optimization for perl 5.)
Re: [perl] The Sort Problem
On Thu, 12 Feb 2004 15.40, Joe Gottman wrote:
This is unrelated to the problem you mentioned, but there is another
annoying problem with sort as it is currently defined. If you have an
@array and you want to replace it with the sorted version, you have to type
@array = sort @array;
Besides being long-winded, this causes Perl to make an unnecessary copy of
the array. It would be nice calling if sort (or reverse, or other similar
functions) in void context resulted in in-place modification of the array
that was input.
I just know that this has come up before . . . I don't remember whether it was
consensus[1] or just my wishful thinking that this would make code like:
sub foo
{
my $listref = shift;
# other stuff...
# return sorted list.
sort @$listref;
}
morally ambiguous[2], because that sort is being called in whatever context
the function call was in, which could be miles away.
I'd suggest that an in-place sort have a marginally different name, but the
rubyometer is already redlined as it is.
(Even more OT: I dislike the scoping rules for named sorting subroutines in
Perl 5. It means you can't do questionable things like this:
# A common function used all over the place.
sub onewayorother { $direction * ($a = $b) }
# much later ...
my $direction = -1;
my @arr = sort onewayorother (5,7,9);
The more I look at that, the more I think it's a stupid example, but I have a
vivid memory of being upset about it several years ago, when I wasn't a very
good programmer. This is looking less like a whinge and more like a
confession. Move along, nothing more to see here.)
[1] If, by consensus, you mean Larry Said No.
[2] Not semantically ambiguous, because it isn't.
--
Debbie Pickett
http://www.csse.monash.edu.au/~debbiep
[EMAIL PROTECTED]
Re: The Sort Problem
Luke Palmer wrote:
Any other ideas?
How about something like this, modulo any errors in my Perl 6 syntax?
sub sort(?cmp = infix:cmp, +$key, +$desc, [EMAIL PROTECTED]) { ... }
I think that allows all of these:
# P5: @sorted = sort @unsorted;
@sorted = sort @unsorted;
The simplest case is the same as the Perl 5, which seems a pleasant feature.
# P5: @sorted = sort { $a = $b } @unsorted;
@sorted = sort { $^a = $^b } @unsorted; # or:
@sorted = sort infix:= == @unsorted;
This also seems reasonable.
# P5: @sorted = sort { $a-foo('bar')-compute = $b-foo('bar')-compute }
# @unsorted
# or: @sorted = map { $_-[1] }
# sort { $a-[0] =? $b-[0] }
# map { [ $_-foo('bar')-compute, $_ ] }
# @unsorted
@sorted = sort infix:=, key = { $_.foo('bar').compute } == @unsorted;
I think my suggestion wins big here. We've only had to specify how to
extract the key, and sort itself takes care of everything else. And it looks
to me like this sort function has enough information about the programmer's
intent for it to optimise in all sorts of exciting ways -- it should be able
to do the equivalent of the GRT internally, for example.
Just for kicks, this one demonstrates all the features. It's the same as
before, but in descending order:
@unsorted
== sort infix:=, desc = 1, key = { $_.foo('bar').compute }
== @sorted;
What problems can anyone spot with this suggestion?
--
Aaron Crane * GBdirect Ltd.
http://training.gbdirect.co.uk/courses/perl/
Re: The Sort Problem
...
so here is a (very rough and probably broken) syntax idea building on
that:
sort :key { :descend :string .foo('bar').substr( 10, 3) }
:key { :int .foo('baz') }
:key { :float .foo('amount') } @unsorted ;
I see a kind of problem here: If the parts of the key are not fixed length but
can vary you can put them in strings *only* after processing all and
verifying the needed length.
Example:
sort :key { :descend :string .foo('bar') }
:key { :int .foo('baz') }
:key { :float .foo('amount') } @unsorted ;
Now .foo('bar') isn't bounded with any length - so you don't know how much
space to reserve.
And I believe that
- generating keys on every list element
- storing them into a array (array of array) and
- after having processed all checking the length, and
- now generate the to-be-sorted-strings
- sort
isn't the optimal way.
BTW: this requires that *all* keys are generated.
In cases like
- by name,
- by age,
- by height,
- by number of toes left,
- and finally sort by the social security number
most of the extractions (and possibly database-queries of calculations or
whatever) will not be done - at least in the current form of
sort { $a-{name} cmp $b-{name} ||
$a-{age} = $b-{age} ||
...
That is to say, I very much like the syntax you propose, but I'm not sure if
pre-generating *every* key-part is necessarily a speed-up.
If there are expensive calculations you can always cut them short be
pre-calculating them into a hash by object, and just query this in sort.
Also I fear that the amount of memory necessary to sort an array of length N
is not N*2 (unsorted, sorted), but more like N*3 (unsorted, keys, sorted),
which could cause troubles on bigger arrays
Regards,
Phil
Traits: to renew OO inheritance in a hacker style discussion
Hi all, I see that i am not alone in my thoughts about classic OO drawbacks. Some smart people created traits for SmallTalk which is something close to what i want. Traits are mechanism, recently proposed by Scharli et al, for factoring Smalltalk class hierarchies. By separating the issue of code reuse from the inheritance hierarchy, traits allow one to avoid problems with methods defined too high in the inheritance hierarchy while sharing common implementation. Early experience with traits in Smalltalk shows that traits are an effective way to improve code sharing in class hierarchies. This positive experience with traits in the untyped Smalltalk world suggests that traits may be useful in statically typed languages too. Scharli et al. recently proposed a mechanism called traits as a way to foster code reuse in objectoriented programs [SDNB03]. They have prototyped the mechanism in the context of the Squeak implementation of Smalltalk. Using traits, they refactored the Smalltalk collection classes achieving a 25% reduction in the number of method implementations and a 10% reduction in source code size [BSD03]. This early experience suggests that traits are a promising mechanism for factoring class hierarchies and supporting code reuse and may be useful for statically typed languages too. The main contribution of this paper is to present a typed calculus of traits that can serve as the foundation for integrating traits into a statically-typed object-oriented language such as JAVA [AG98] or Moby [FR99, FR03]. A trait is collection of named methods. In Smalltalk traits, these methods cannot directly reference instance variables; instead, they must be pure behavior. The methods defined in a tr ait are called the provided methods, while any methods that are referenced, but not provided, are called required methods. An important property of traits is that while they help structure the implementation of classes, they do not affect the inheritance hierarchy. Traits are formed by definition (i.e., listing a collection of method definitions) or by using one of several trait operations: Symmetric sum merges two disjoint traits to create a new trait. Override forms a new trait by layering additional methods over an existing trait. This operation is an asymmetric sum. When one of the new methods has the same name as a method in the original trait, the override operation replaces the original method. Alias creates a new trait by adding a new name for an existing method. Exclusion forms a new trait by removing a method from an existing trait. [Urrh!] Combining the alias and exclusion operations yields a renaming operation, although the renaming is shallow. The other important operation on traits is inheritance, the mechanism whereby traits are integrated with classes. This operation merges a class C, a trait, and additional fields and methods to form a new subclass of C. Often, the additional methods provide access to the newly added fields. The additional methods, plus the methods inherited from C, provide the required methods of the trait. An important aspect of traits is that the methods of a trait are only loosely coupled; they can be removed and replaced by other implementations. In this way traits are a lighter-weight mechanism than either multiple inheritance or mixins. grabbed from http://www.cs.uchicago.edu/research/publications/techreports/TR-2003-13 see also http://www.iam.unibe.ch/~schaerli/smalltalk/traits/traitsPrototype.htm Hope that it is something interesting for real Perl hackers who will make Perl 6 the best language ever. -Dmitry Dorofeev.
Re: The Sort Problem
On Thu, 2004-02-12 at 01:59, Uri Guttman wrote:
sorry about the confusion. read the paper at:
http://www.sysarch.com/perl/sort_paper.html
All of which stops being a concern if you have a sort variant that works
on pairs in the first place. Perl _5_ code follows:
sub sortpairs(@) {
my $comp = shift;
my %pairs = @_;
return map {$pairs{$_}} sort {$comp-($a)} keys %pairs;
}
@new1 = sortpairs {$a = $b} map {($_-computekey,$_)} @old1;
@new2 = sortpairs {$a cmp $b} map {(lc($_),uc($_))} @old2;
as you can see, you can perform any key extraction you like in the map
portion (which just returns key/value pairs) and sortpairs' job is just
to compare the keys and return the resulting sorted values.
No Perl 6 here, move along ;-)
Perl 6 could contribute here by making it cheaper to construct/pass the
keys, but that's about it.
--
Aaron Sherman [EMAIL PROTECTED]
Senior Systems Engineer and Toolsmith
It's the sound of a satellite saying, 'get me down!' -Shriekback
signature.asc
Description: This is a digitally signed message part
Re: The Sort Problem
On Thu, 2004-02-12 at 08:43, Aaron Sherman wrote:
sub sortpairs(@) {
my $comp = shift;
my %pairs = @_;
return map {$pairs{$_}} sort {$comp-($a)} keys %pairs;
}
Doh... it's early for me. That's Csort {$comp-()} with no parameter.
The fact that $a and $b are dynamically scoped in Perl 5 helps out here.
--
Aaron Sherman [EMAIL PROTECTED]
Senior Systems Engineer and Toolsmith
It's the sound of a satellite saying, 'get me down!' -Shriekback
signature.asc
Description: This is a digitally signed message part
Re: Traits: to renew OO inheritance in a hacker style discussion
On Thu, 2004-02-12 at 08:14, Dmitry Dorofeev wrote: I see that i am not alone in my thoughts about classic OO drawbacks. Some smart people created traits for SmallTalk which is something close to what i want. Perhaps I'm slow, but I don't see the difference between a trait and a Java interface other than the fact that traits appear to be more of a run-time construct. Java interfaces are actually a very nice compromise between multiple and single inheritance. -- Aaron Sherman [EMAIL PROTECTED] Senior Systems Engineer and Toolsmith It's the sound of a satellite saying, 'get me down!' -Shriekback signature.asc Description: This is a digitally signed message part
Re: Traits: to renew OO inheritance in a hacker style discussion
Aaron Sherman wrote: Perhaps I'm slow, but I don't see the difference between a trait and a Java interface other than the fact that traits appear to be more of a run-time construct. Java interfaces are actually a very nice compromise between multiple and single inheritance. You can not get rid of the method with Java interface. Plus, interface is only declaration, you must implement methods in each class which use interface. AFAIK (last touched Java 5 years ago) Look at example: While the purpose of this paper is not to argue the merits of traits per se (see [SDNB03, BSD03] for such arguments), it is helpful to understand the motivation for traits. In languages with single inheritance, such as Smalltalk, it is often the case that inheritance does not provide sufficient flexibility for structuring a class hierarchy. Consider the case of two classes in different subtrees of the inheritance hierarchy and assume that they both implement some common protocol. If this protocol is not implemented by a common superclass, then each class must provide its own implementation, which results in code duplication. On the other hand, if we lift the implementation of the protocol up to the common superclass, we pollute the interface of the superclass, which affects all of its subclasses. Furthermore, if the protocol is defined by building on methods defined in intermediate classes, we will have to add these methods to the common superclass as well. This problem resul ts from the dual nature of classes. Classes serve as both object generators and as superclasses. In the former case, the implementation of a class must be complete, whereas in the latter case the class implementation may have abstract methods that are implemented by a subclass. Traits provide a mechanism to separate these two aspects of classes and allow code to be reused across the class hierarchy. Multiple inheritance [Str94] and mixins [BC90, FKF98] represent two other attempts to solve this problem, but they both introduce semantic complexities and ambiguities (e.g., multiple copies of instance variables in the case of multiple inheritance, and problems with the order of method definition in the case of mixins) [SDNB03]. It is from link i provided in previous post. -Dmitry Dorofeev.
Re: [perl] The Sort Problem
At 11:40 PM -0500 2/11/04, Joe Gottman wrote: This is unrelated to the problem you mentioned, but there is another annoying problem with sort as it is currently defined. If you have an @array and you want to replace it with the sorted version, you have to type @array = sort @array; That would seem to be a place for more explicit, and specific, behaviour. Since we're going everything is an object then it's just a matter of: @array.sort_in_place; and making sure that the array role provides the appropriate method. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Traits: to renew OO inheritance in a hacker style discussion
Yes, that's a very good paper, which is why Perl 6 now has something called Roles, which are intended to degenerate either to Traits or Interfaces. My take on it is that Roles' most important, er, role will be to abstract out the decision to compose or delegate. But we'd like them to function as interfaces when the Role is abstract, and we'd like them to function as Traits when you don't happen to specify any state attributes. But for hiding the delegation decision, you at least have to allow the amount of state that lets you remember the object you're delegating to. Of course, the Traits paper didn't go into traits with state, though it did mention it as a future research topic. We're just doing that future research for them. :-) By the way, we distinguish Traits from traits (which are compile-time properties applied by is. To apply a Role we use does. Larry
Re: Traits: to renew OO inheritance in a hacker style discussion
On Thu, 2004-02-12 at 05:52, Aaron Sherman wrote: Perhaps I'm slow, but I don't see the difference between a trait and a Java interface other than the fact that traits appear to be more of a run-time construct. The easy answer is that interfaces completely suck while traits don't. :) Seriously though, Java interfaces add an alternate type system with an alternate syntax for querying. They also don't allow any sort of reasonable code re-use. Effectively, they're abstract multiply-inheritable base classes with a different name because Multiple Inheritance Is Bad! On a conceptual level, the different syntax is the worst crime because it reinforces the idea that the important question about an object is What is this object's position in a class hierarchy?, not Does this object have the same semantic meaning for these operations as I expect it to have? Then again, I usually explain it in terms of sucks, not don't even acknowledge the real problem. -- c
Re: Traits: to renew OO inheritance in a hacker style discussion
On Thu, Feb 12, 2004 at 11:03:57AM -0800, chromatic wrote: : On a conceptual level, the different syntax is the worst crime because : it reinforces the idea that the important question about an object is : What is this object's position in a class hierarchy?, not Does this : object have the same semantic meaning for these operations as I expect : it to have? What I'm currently thinking about is a does predicate that tells you if an object/class does a particular role completely. If you pull part of a role into a class, it returns false, because it doesn't do the complete role. However, if you use like instead, it returns a number between 0 and 1 telling you what fraction of the role's methods it uses. So you can ask if your object is more like a Dog or a Tree. Unless someone comes up with a better idea, of course. Obviously .does() is redundant with .like() == 1. But it seems like a useful redundancy. Larry
Re: The Sort Problem
On Thu, Feb 12, 2004 at 12:07:37PM +0100, Ph. Marek wrote:
: ...
: so here is a (very rough and probably broken) syntax idea building on
: that:
:
: sort :key { :descend :string .foo('bar').substr( 10, 3) }
:
: :key { :int .foo('baz') }
: :key { :float .foo('amount') } @unsorted ;
: I see a kind of problem here: If the parts of the key are not fixed length but
: can vary you can put them in strings *only* after processing all and
: verifying the needed length.
I think this is easily solved by sorting on a list of strings rather than a
single string.
: - generating keys on every list element
: - storing them into a array (array of array) and
: - after having processed all checking the length, and
: - now generate the to-be-sorted-strings
: - sort
:
: isn't the optimal way.
: BTW: this requires that *all* keys are generated.
: In cases like
: - by name,
: - by age,
: - by height,
: - by number of toes left,
: - and finally sort by the social security number
Not if you lazily add strings to the list of strings mentioned above.
: That is to say, I very much like the syntax you propose, but I'm not sure if
: pre-generating *every* key-part is necessarily a speed-up.
:
: If there are expensive calculations you can always cut them short be
: pre-calculating them into a hash by object, and just query this in sort.
Another approach is to declare a function that is cached, I suppose.
: Also I fear that the amount of memory necessary to sort an array of length N
: is not N*2 (unsorted, sorted), but more like N*3 (unsorted, keys, sorted),
: which could cause troubles on bigger arrays
We'll just use virtual memory. :-)
Larry
Re: Traits: to renew OO inheritance in a hacker style discussion
On Thu, 2004-02-12 at 11:49, Larry Wall wrote: What I'm currently thinking about is a does predicate that tells you if an object/class does a particular role completely. If you pull part of a role into a class, it returns false, because it doesn't do the complete role. However, if you use like instead, it returns a number between 0 and 1 telling you what fraction of the role's methods it uses. So you can ask if your object is more like a Dog or a Tree. Unless someone comes up with a better idea, of course. Obviously .does() is redundant with .like() == 1. But it seems like a useful redundancy. Is it more useful to find the Dog-like-ness of a class or the notion that SomeClass.bark() is semantically Dog-like, not Tree-like? I expect to care more that the object does something Dog-like with the methods I'm about to call on it than how Dog-like it is in general. Maybe that's slicing does() way too thin, but like() seems to care an awful lot about the implementation of how some class does some role. -- c
Re: Traits: to renew OO inheritance in a hacker style discussion
On Thu, Feb 12, 2004 at 12:02:50PM -0800, chromatic wrote: : Is it more useful to find the Dog-like-ness of a class or the notion : that SomeClass.bark() is semantically Dog-like, not Tree-like? I expect we'd use .can() for method-based queries. : I expect to care more that the object does something Dog-like with the : methods I'm about to call on it than how Dog-like it is in general. : Maybe that's slicing does() way too thin, but like() seems to care an : awful lot about the implementation of how some class does some role. I only see like() as counting the methods available through the public contract to determine its percentage. Something you could do by hand with .can(). But there wouldn't be much point in putting it in if people won't use it. On the other hand, if people want it and it's not there, they'll reinvent it, poorly. Larry
Re: Traits: to renew OO inheritance in a hacker style discussion
Larry Wall wrote: I only see like() as counting the methods available through the public contract to determine its percentage. Something you could do by hand with .can(). But there wouldn't be much point in putting it in if people won't use it. On the other hand, if people want it and it's not there, they'll reinvent it, poorly. I'd use it for marshalling objects composed of many things to something that makes sense to someone else's idea of what they should be, eg an XML Schema. Pick what it's most alike to and marshall as that. -- Robin Berjon
Re: The Sort Problem
Aaron Crane writes:
Luke Palmer wrote:
Any other ideas?
How about something like this, modulo any errors in my Perl 6 syntax?
sub sort(?cmp = infix:cmp, +$key, +$desc, [EMAIL PROTECTED]) { ... }
I think that allows all of these:
# P5: @sorted = sort @unsorted;
@sorted = sort @unsorted;
The simplest case is the same as the Perl 5, which seems a pleasant feature.
This is a feature that, IMO, we can not do without. I still do things
like:
print $_: %hash{$_} for sort keys %hash;
All the time, and I don't want to give that up for some clearer
syntax, as there is no such thing.
# P5: @sorted = sort { $a = $b } @unsorted;
@sorted = sort { $^a = $^b } @unsorted; # or:
@sorted = sort infix:= == @unsorted;
This also seems reasonable.
# P5: @sorted = sort { $a-foo('bar')-compute = $b-foo('bar')-compute }
# @unsorted
# or: @sorted = map { $_-[1] }
# sort { $a-[0] =? $b-[0] }
# map { [ $_-foo('bar')-compute, $_ ] }
# @unsorted
@sorted = sort infix:=, key = { $_.foo('bar').compute } == @unsorted;
Ok, I have to say, that's pretty good. Er, really good. I like it a
lot.
I think my suggestion wins big here. We've only had to specify how to
extract the key, and sort itself takes care of everything else. And it looks
to me like this sort function has enough information about the programmer's
intent for it to optimise in all sorts of exciting ways -- it should be able
to do the equivalent of the GRT internally, for example.
Just for kicks, this one demonstrates all the features. It's the same as
before, but in descending order:
@unsorted
== sort infix:=, desc = 1, key = { $_.foo('bar').compute }
== @sorted;
What problems can anyone spot with this suggestion?
I don't like the Cdesc flag. But I can't, at the moment, think of any
way around it short of:
@unsorted
== sort { $^b = $^a }, key = { .foo('bar').compute }
== @sorted
Which people have made pretty clear that they don't like.
Oh, by the way, your Perl 6 syntax is immaculate. Bravo :-)
Luke
Re: The Sort Problem
LP == Luke Palmer [EMAIL PROTECTED] writes:
# P5: @sorted = sort { $a-foo('bar')-compute = $b-foo('bar')-compute }
# @unsorted
# or: @sorted = map { $_-[1] }
# sort { $a-[0] =? $b-[0] }
# map { [ $_-foo('bar')-compute, $_ ] }
# @unsorted
@sorted = sort infix:=, key = { $_.foo('bar').compute } == @unsorted;
LP Ok, I have to say, that's pretty good. Er, really good. I like it a
LP lot.
how do you select descending order? and how do you selecte that per key?
you can't provide a binary operator without also providing the
order. and what about different key types? the = and cmp operators are
not enough information needed to do complex sorts. collating sequences
are another issue. you need to have that info on a perl key basis.
I think my suggestion wins big here. We've only had to specify how
to extract the key, and sort itself takes care of everything else.
And it looks to me like this sort function has enough information
about the programmer's intent for it to optimise in all sorts of
exciting ways -- it should be able to do the equivalent of the GRT
internally, for example.
sort can't figure it out without you telling it things. you need more
than just key extraction.
Just for kicks, this one demonstrates all the features. It's the same as
before, but in descending order:
@unsorted
== sort infix:=, desc = 1, key = { $_.foo('bar').compute }
== @sorted;
What problems can anyone spot with this suggestion?
multiple keys with each having different comparisons and different sort
orders.
LP @unsorted
LP == sort { $^b = $^a }, key = { .foo('bar').compute }
LP == @sorted
LP Which people have made pretty clear that they don't like.
as i have said before. needing to have $a and $b in the correct order is
bug prone and confusing to many.
uri
--
Uri Guttman -- [EMAIL PROTECTED] http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs http://jobs.perl.org
Re: The Sort Problem
PM == Ph Marek [EMAIL PROTECTED] writes:
...
so here is a (very rough and probably broken) syntax idea building on
that:
sort :key { :descend :string .foo('bar').substr( 10, 3) }
:key { :int .foo('baz') }
:key { :float .foo('amount') } @unsorted ;
PM I see a kind of problem here: If the parts of the key are not
PM fixed length but can vary you can put them in strings *only* after
PM processing all and verifying the needed length.
varying keys has no effect on this. you still build up a merged key of
whatever length is needed for each record. perl5 does that with pack or
.= or sprintf (all used in variants of the GRT).
PM Example:
PM sort :key { :descend :string .foo('bar') }
PM :key { :int .foo('baz') }
PM :key { :float .foo('amount') } @unsorted ;
PM Now .foo('bar') isn't bounded with any length - so you don't know how much
PM space to reserve.
who needs to reserve space? you just let the guts do a realloc like p5
does now.
PM And I believe that
PM - generating keys on every list element
PM - storing them into a array (array of array) and
PM - after having processed all checking the length, and
PM - now generate the to-be-sorted-strings
PM - sort
PM isn't the optimal way.
PM BTW: this requires that *all* keys are generated.
PM In cases like
PM - by name,
PM - by age,
PM - by height,
PM - by number of toes left,
PM - and finally sort by the social security number
PM most of the extractions (and possibly database-queries of calculations or
PM whatever) will not be done - at least in the current form of
PM sort { $a-{name} cmp $b-{name} ||
PM$a-{age} = $b-{age} ||
PM ...
PM That is to say, I very much like the syntax you propose, but I'm
PM not sure if pre-generating *every* key-part is necessarily a
PM speed-up.
see the paper for more on that. the work you do in the callback, even if
you only do the first compare is O(N log N). in large sorts that will
outweigh the O(N) work on extracting the keys one time.
and as with all algorithms, real world cases will differ. short sorts
can be faster with complex comparisons because of the initial
overhead. maybe the internal code can decide to do that instead of a GRT
based on the sort array size. the key extract code is the same in both
cases so that would be an interesting optimization.
PM If there are expensive calculations you can always cut them short
PM be pre-calculating them into a hash by object, and just query this
PM in sort.
again, the goal is to eliminate work in the comparison. but as i said,
this is an implementation problem. we should focus on the language level
needs of the sort func and not how it is done internally. i shouldn't
have brought up the internal design here.
PM Also I fear that the amount of memory necessary to sort an array
PM of length N is not N*2 (unsorted, sorted), but more like N*3
PM (unsorted, keys, sorted), which could cause troubles on bigger
PM arrays
as larry said, virtual memory. and there are ways to reduce the copies
internally with pointers (something p5 couldn't do at p5 code level).
other than copying the extracted keys, you could leave the original
array alone and sort it in place by indexing it based on the sorted
pointers. and since the records will all be the same PMC type (usually),
you could just swap the array's pointers and not move any data
around. so no extra copies would be made other than key extraction.
uri
--
Uri Guttman -- [EMAIL PROTECTED] http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs http://jobs.perl.org
Re: The Sort Problem
Luke Palmer wrote:
Aaron Crane writes:
@unsorted
== sort infix:=, desc = 1, key = { $_.foo('bar').compute }
== @sorted;
I don't like the Cdesc flag. But I can't, at the moment, think of any
way around it short of:
@unsorted
== sort { $^b = $^a }, key = { .foo('bar').compute }
== @sorted
Which people have made pretty clear that they don't like.
One option might be an 'rsort' function, but I think that's somewhat lacking
in the taste department.
Another might be as simple as
@unsorted == sort == reverse == @sorted;
But I can see an argument that C == reverse is quite a large code
burden for something so conceptually simple.
I have one other idea, but I can't decide if I like it:
@unsorted == sort rinfix:cmp == @sorted;
That is, rinfix: (or some other name) is like infix:, but gives you a
function that reverses its arguments before actually running the operator.
Perhaps it could even be implemented as a macro.
--
Aaron Crane * GBdirect Ltd.
http://training.gbdirect.co.uk/courses/perl/
Re: The Sort Problem
AC == Aaron Crane [EMAIL PROTECTED] writes: AC One option might be an 'rsort' function, but I think that's AC somewhat lacking in the taste department. AC Another might be as simple as AC @unsorted == sort == reverse == @sorted; again, reverse order needs to be on a per key basis. the problem we are wrangling is how to support multiple keys in a clean syntactical way. AC @unsorted == sort rinfix:cmp == @sorted; AC That is, rinfix: (or some other name) is like infix:, but gives you a AC function that reverses its arguments before actually running the operator. AC Perhaps it could even be implemented as a macro. again, confusing. why should the order of a binary operator mean so much? the order of a sort key is either ascending or descending. that is what coders want to specify. translating that to the correct operator (cmp or =) and the correct binary order is not the same as specifying the key sort order and key type (int, string, float). uri -- Uri Guttman -- [EMAIL PROTECTED] http://www.stemsystems.com --Perl Consulting, Stem Development, Systems Architecture, Design and Coding- Search or Offer Perl Jobs http://jobs.perl.org
Re: The Sort Problem
Aaron Crane writes:
I have one other idea, but I can't decide if I like it:
@unsorted == sort rinfix:cmp == @sorted;
That is, rinfix: (or some other name) is like infix:, but gives you a
function that reverses its arguments before actually running the operator.
Perhaps it could even be implemented as a macro.
Like this one?
macro rinfix($op)
is parsed(/ \: (.*?) before: [\s(] /)
{
return {
- $a, $b {
(infix:$op).($b, $a)
}
}
}
Luke
Re: The Sort Problem
[EMAIL PROTECTED] (Aaron Crane) writes: One option might be an 'rsort' function, but I think that's somewhat lacking in the taste department. Agreed. Another might be as simple as @unsorted == sort == reverse == @sorted; @sorted == sort == @unsorted, no? ;) @unsorted == sort rinfix:cmp == @sorted; That is, rinfix: (or some other name) is like infix:, but gives you a function that reverses its arguments before actually running the operator. Perhaps it could even be implemented as a macro. I like this; it reminds me of the games you have to play with determining what do to with binary operators whose operands are overloaded in different classes. -- Do not go gentle into that good night/Rage, rage against the dying of the light
Re: The Sort Problem
Perhaps something like:
@sorted = sort { infix:= map { scalar $_.foo('bar').compute } @^_ } }
@data
I'm not entirely sure it's readability is better than yours, though.
Dave.
Luke Palmer [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]
I've been thinking about this problem which comes up in my code a lot:
@sorted = sort { $^a.foo('bar').compute = $^b.foo('bar').compute }
@unsorted;
Often the expressions on each side are even longer than that. But one
thing remains: both sides are exactly the same, substitute a $^b for a
$^a.
I can see a couple less-than-desirable ways around this redundancy:
@sorted = sort { infix:=( *($^a, $^b)».foo('bar').compute ) }
@unsorted;
Which doesn't work if .compute returns a list... not to mention its
horrible ugliness. Another is to define a variant of sort (haven't had
much practice with A6 material recently; here we go!):
multi sub sort (block($) = { $_ } : [EMAIL PROTECTED]) {
sort { block($^a) cmp block($^b) } @data;
}
@sorted = sort { .foo('bar').compute } @unsorted;
Which has the disadvantage of forcing you to use Ccmp and forcing an
ascending sort.
Any other ideas? Is a more general solution necessary?
Luke
Re: The Sort Problem
On Thu, 2004-02-12 at 15:46, Uri Guttman wrote:
LP == Luke Palmer [EMAIL PROTECTED] writes:
LP Ok, I have to say, that's pretty good. Er, really good. I like it a
LP lot.
how do you select descending order? and how do you selecte that per key?
you can't provide a binary operator without also providing the
order. and what about different key types? the = and cmp operators are
not enough information needed to do complex sorts. collating sequences
are another issue. you need to have that info on a perl key basis.
You know, I have trouble typing per when I'm thinking perl too ;-)
I think my example addressed all of your concerns, and did it in Perl 5.
Once again, that was:
sub sortpairs(@) {
my $comp = shift;
my %pairs = @_;
return map {$pairs{$_}} sort {$comp-()} keys %pairs;
}
@new1 = sortpairs {$a = $b} map {($_-computekey,$_)} @old1;
@new2 = sortpairs {$a cmp $b} map {(lc($_),uc($_))} @old2;
So, in order, your questions were:
* how do you select descending order?
You reverse the $a and $b in the first parameter to sortpairs
* and how do you selecte that per key?
Ok, I was only addressing one key. But, it's not hard to
generalize the idea, and certainly Perl 6 gives you the tools to
do so easily.
* you can't provide a binary operator without also providing the
order.
Correct
* and what about different key types? the = and cmp operators
are not enough information needed to do complex sorts.
That's fine, you can plug in a call to Alien::Headed::Babies
inside the closure for all I care.
* collating sequences are another issue. you need to have that
info on a perl key basis.
Give me an example?
* multiple keys with each having different comparisons and
different sort orders.
Ok let's delve into it then:
sub sortpairs(@){
my $comp = shift;
my @elements = @_;
return map {my $e=$elements[$_];$e-[$#{$e}]} sort {
my @akeys = @{$elements[$a]}[0..$#{$elements[$a]}-1];
my @bkeys = @{$elements[$b]}[0..$#{$elements[$b]}-1];
for(my $i=0;$i@akeys;$i++) {
my $dir = $comp-($akey[$i],$bkey[$i]);
return $dir if $dir;
}
return 0;
} 1..scalar(@elements);
}
@new1 = sortpairs {$_[0] = $_[1]} map {[$_,$_]} @old1;
@new2 = sortpairs {$_[0] = $_[1] || $_[4] cmp $_[3]} map {[getkeys($_),$_]}
@old2;
The second example really illustrates the point that you can swap the
direction of key order and mechanism to compare them at your whim.
Now, you just need to call sortpairs with any array of arrays of keys
(with trailing value).
--
Aaron Sherman [EMAIL PROTECTED]
Senior Systems Engineer and Toolsmith
It's the sound of a satellite saying, 'get me down!' -Shriekback
Re: The Sort Problem
AS == Aaron Sherman [EMAIL PROTECTED] writes:
AS On Thu, 2004-02-12 at 15:46, Uri Guttman wrote:
how do you select descending order? and how do you selecte that per
key?
you can't provide a binary operator without also providing the
order. and what about different key types? the = and cmp
operators are not enough information needed to do complex
sorts. collating sequences are another issue. you need to have that
info on a perl key basis.
AS I think my example addressed all of your concerns, and did it in Perl 5.
AS Once again, that was:
AS sub sortpairs(@) {
AS my $comp = shift;
AS my %pairs = @_;
AS return map {$pairs{$_}} sort {$comp-()} keys %pairs;
AS }
AS @new1 = sortpairs {$a = $b} map {($_-computekey,$_)} @old1;
AS @new2 = sortpairs {$a cmp $b} map {(lc($_),uc($_))} @old2;
AS So, in order, your questions were:
AS * how do you select descending order?
AS You reverse the $a and $b in the first parameter to sortpairs
i find that a poor solution. the $a cmp $b isn't needed in the ascending
case at all. a descending marker per key is better as it reflects the
results desired and not how it gets done. the reversing of $a and $b
requires the coder to understand sort comparison callbacks. it is
implementation exposed.
AS * and how do you selecte that per key?
AS Ok, I was only addressing one key. But, it's not hard to
AS generalize the idea, and certainly Perl 6 gives you the tools to
AS do so easily.
i haven't seen any proposals other than mine (which is bad syntax but
good semantics) for this. and if you have multiple keys with each having
a $a = $b in there it will be very noisy.
AS * you can't provide a binary operator without also providing the
AS order.
AS Correct
a single descending marker is simpler and better semantics.
AS * and what about different key types? the = and cmp operators
AS are not enough information needed to do complex sorts.
AS That's fine, you can plug in a call to Alien::Headed::Babies
AS inside the closure for all I care.
there are only a short list of key comparisons possible, int, string,
float and maybe unicode. i separate int from float since they do have
different internals in the GRT. it is one area where you do expose
stuff. otherwise you could just use number.
AS * collating sequences are another issue. you need to have that
AS info on a perl key basis.
AS Give me an example?
simple. pick almost any language char set other than US ascii. many have
special collating sequences. i am not anything close to a unicode expert
but i have seen this issue. in fact setting the LANG (or some other)
environment variable will affect many programs by changing the collating
order.
AS * multiple keys with each having different comparisons and
AS different sort orders.
AS Ok let's delve into it then:
AS sub sortpairs(@){
AS my $comp = shift;
AS my @elements = @_;
AS return map {my $e=$elements[$_];$e-[$#{$e}]} sort {
AS my @akeys = @{$elements[$a]}[0..$#{$elements[$a]}-1];
why the -1? that looks like:
my @akeys = @{$elements[$a]} ;
pop @akeys ;
pop @akeys ;
AS my @bkeys = @{$elements[$b]}[0..$#{$elements[$b]}-1];
AS for(my $i=0;$i@akeys;$i++) {
ASmy $dir = $comp-($akey[$i],$bkey[$i]);
ASreturn $dir if $dir;
AS }
AS return 0;
AS } 1..scalar(@elements);
AS }
that is scary. do you realize that the sort block will be called for
each comparison?
AS @new1 = sortpairs {$_[0] = $_[1]} map {[$_,$_]} @old1;
AS @new2 = sortpairs {$_[0] = $_[1] || $_[4] cmp $_[3]} map
AS {[getkeys($_),$_]} @old2;
where is getkeys defined? how do you know what indexes to use for each
comparison? what happened to $_[2]? your call to $comp is passed 2
arguments but the second example accesses 4 arguments.
AS The second example really illustrates the point that you can swap the
AS direction of key order and mechanism to compare them at your whim.
AS Now, you just need to call sortpairs with any array of arrays of keys
AS (with trailing value).
add a third key to that. quickly!
a more straightforward api (which is close to what i will do in
Sort::GRT) is (p5 code)
my $sort = Sort::GRT-new(
keys= [
{ descending = 1,
type = float,
extract = '$_-{amount},
},
{ extract = 'substr( $_-{date}, 0, 4)' },
]
) ;
my @sorted = $sort-do_it( @unsorted ) ;
$sort-do_it_inplace( [EMAIL PROTECTED] ) ;
Re: The Sort Problem
On Thu, Feb 12, 2004 at 09:37:37PM +, Simon Cozens wrote: : [EMAIL PROTECTED] (Aaron Crane) writes: : That is, rinfix: (or some other name) is like infix:, but gives you a : function that reverses its arguments before actually running the operator. : Perhaps it could even be implemented as a macro. : : I like this; it reminds me of the games you have to play with determining : what do to with binary operators whose operands are overloaded in different : classes. Which we're trying very hard to get away from in Perl 6...which reminds me, I have to put something about that into A12... Larry
Re: The Sort Problem
On Thu, Feb 12, 2004 at 04:29:58PM -0500, Uri Guttman wrote: : again, confusing. why should the order of a binary operator mean so : much? the order of a sort key is either ascending or descending. that is : what coders want to specify. translating that to the correct operator : (cmp or =) and the correct binary order is not the same as specifying : the key sort order and key type (int, string, float). Uri is dead on with this one, guys. Larry
Re: Traits: to renew OO inheritance in a hacker style discussion
Larry Wall wrote: What I'm currently thinking about is a does predicate that tells you if an object/class does a particular role completely. If you pull part of a role into a class, it returns false, because it doesn't do the complete role. However, if you use like instead, it returns a number between 0 and 1 telling you what fraction of the role's methods it uses. So you can ask if your object is more like a Dog or a Tree. Unless someone comes up with a better idea, of course. Obviously .does() is redundant with .like() == 1. But it seems like a useful redundancy. I'd rather they not be redundant. Instead, Cdoes would check to see if the role in question is ever directly referenced anywhere in the class definition (or in any of its parent class' definitions), whereas Clike would check to see how many of the methods and/or attributes supplied and/or demanded by the role are available to the class. Thus, a class that includes a Cbark method but no CDog role will return a not purely false value for the Clike predicate, but would return false for the Cdoes predicate. This would tell you that the class can bark, but not neccessarily like a Dog. Whereas if it answers true to Cdoes, you know that when it barks, it will likely do so in the manner that a Dog does. Furthermore, I have my doubts about how useful a zero-to-one number would be as a return value for Clike. Personally, I'd rather get a junction of Ccan and Chas predicate calls, which I could then query to find out exactly how the class is Clike the role in question, and how it differs. That is, C$x like $y := Cany($x »can« @methods($y)) or any($x »has« @attributes($y)) or Call($x »can« @methods($y)) and all($x »has« @attributes($y)) or maybe just C$x »can« @methods($y), $x »has« @attributes($y) = Jonathan Dataweaver Lang __ Do you Yahoo!? Yahoo! Finance: Get your refund fast by filing online. http://taxes.yahoo.com/filing.html
dynamic arguments (was: The Sort Problem)
Jonathan Lang wrote:
Luke Palmer wrote:
I've been thinking about this problem which comes up in my code a lot:
@sorted = sort { $^a.foo('bar').compute = $^b.foo('bar').compute}
@unsorted;
Often the expressions on each side are even longer than that. But one
thing remains: both sides are exactly the same, substitute a $^b for
a $^a.
The problem, then, isn't specific to sort; it happens any time that you
find yourself needing to do the same things to multiple arguments. As
such, the solution ought to be more general than just sort.
You're looking for something to the effect of:
@sorted = sort { parameters($^a = $^b).foo('bar').compute }
That is, you need a way to factor C.foo('bar').compute out from each
of the arguments that it applies to. For list arguments, this is
straightforward: pipe the list arguments through a map before you pipe
them into the routine. A similar approach could be used with named
arguments. The problem comes when you deal with positional arguments.
How about including something similar to ==, but which binds the elements
of the list to the various positional parameters? For instance:
@sorted = sort {infix:= args map {$_.foo('bar').compute}, $^a, $^b }
@unsorted;
Where
@x = $a, $b, $c;
routine args @x;
is equivelent to
routine $a, $b, $c;
=
Jonathan Dataweaver Lang
__
Do you Yahoo!?
Yahoo! Finance: Get your refund fast by filing online.
http://taxes.yahoo.com/filing.html
Re: dynamic arguments (was: The Sort Problem)
Jonathan Lang writes:
How about including something similar to ==, but which binds the elements
of the list to the various positional parameters? For instance:
@sorted = sort {infix:= args map {$_.foo('bar').compute}, $^a, $^b }
@unsorted;
Where
@x = $a, $b, $c;
routine args @x;
is equivelent to
routine $a, $b, $c;
We already have that. It's spelled:
routine [EMAIL PROTECTED];
Or
routine * == @x;
Luke
Re: dynamic arguments (was: The Sort Problem)
Luke Palmer wrote:
Jonathan Lang writes:
How about including something similar to ==, but which binds the
elements of the list to the various positional parameters? For
instance:
@sorted = sort {infix:= args map {$_.foo('bar').compute},
$^a, $^b } @unsorted;
Where
@x = $a, $b, $c;
routine args @x;
is equivelent to
routine $a, $b, $c;
We already have that. It's spelled:
routine [EMAIL PROTECTED];
Or
routine * == @x;
Then you've got your solution:
@sorted = sort {infix:= * map {$_.foo('bar').compute}, $^a, $^b }
@unsorted;
or
@sorted = sort {($^a, $^b) ==
map {$_.foo('bar').compute} ==
infix:= * } @unsorted;
=
Jonathan Dataweaver Lang
__
Do you Yahoo!?
Yahoo! Finance: Get your refund fast by filing online.
http://taxes.yahoo.com/filing.html
Re: The Sort Problem (was: well, The Sort Problem)
Jonathan Lang writes:
We already have that. It's spelled:
routine [EMAIL PROTECTED];
Or
routine * == @x;
Then you've got your solution:
@sorted = sort {infix:= * map {$_.foo('bar').compute}, $^a, $^b }
@unsorted;
or
@sorted = sort {($^a, $^b) ==
map {$_.foo('bar').compute} ==
infix:= * } @unsorted;
No, I don't think we do. Uri's given some good points in this thread
about specifying what you want out of the sort, instead of some
arbitrary callback interface.
But it needs some major syntax work so it can feel more like it's a part
of the language instead of a library function. Not, mind, that I think
Perl's syntax needs to be changed at all to accommodate.
I'm thinking that Csort might take a list of closures or pairs (with
the value being a closure). I'm still not sure how that separates from
the data to be sorted, but it's probably related to the problem of how
Cfor works in declaration.
The return value of each closure is dispatched into some sort of generic
=, hopefully one that blows up if its arguments are of different
types[1]. That way if you have a method that always returns a number,
you can just leave it alone. Otherwise you're expected to prefix with
the approprate contextifier.
For example:
sort { .foo('bar').compute }, desc = { ~.baz }, @data;
# ascending by default string compares
Pairs don't exactly seem fit here. Maybe we're supposed to think of
these these closures as higher-level 'extractors', and therefore attach
properties to them:
sort { .foo('bar').compute }, { ~.baz } but descending, @data;
Or even something on the value that tells = to negate whatever it
returns:
sort { .foo('bar').compute }, { ~.baz but swap }, @data;
That's starting to expose implementation again, though.
Moving a different direction now. Instead of being honest and saying
that sort does each of these comparisons until one of them is nonzero,
let's pretend that it sorts with respect to the first comparison and
feeds the lists of equal elements into the second comparison, etc.
Sort might then look like:
sub sort (?extract, ?next, [EMAIL PROTECTED])
And our example turns into:
sort { .foo('bar').compute }
{ reverse sort { ~.baz } [EMAIL PROTECTED] }
[EMAIL PROTECTED];
That hurts, especially when there are more than two keys. I'd really
like to do that with the piping operators instead of nested closures,
but that screws with the simple case.
There might be even more ways of looking at this that would result in
more novel syntaxes. Brainstorming required.
Luke
[1] There's something to be said for a generic comparison, but not one
that blows up. Mostly because certain containers want their elements to
be well ordered. But we could just as easily say that elements that
aren't intercompatible with the short-tempered = aren't allowed in
said containers.
