Re: r24325 - docs/Perl6/Spec
On Mon, Dec 15, 2008 at 11:18:54PM -0500, Mark J. Reed wrote: On Mon, Dec 15, 2008 at 5:41 PM, Moritz Lenz mor...@faui2k3.org wrote: I know at least of infix:cmp(Num $a, Num $b) (which does the same as Perl 5's =) and infix:cmp(Pair $a, Pair $b) (which does $a.key cmp $a.key || $a.value cmp $b.value), so numbers and pairs DWIM. Hm. Rakudo doesn't let me cmp pairs at all currently: (a = 2) cmp (a = 10) Multiple Dispatch: No suitable candidate found for 'cmp', with signature 'PP-I' It does now: say (a = 2) cmp (a = 10); -1 S02:1600 somewhat implies that comparison of pairs is based on keys by default, then on values if keys are equal. Rakudo implements this behavior. In particular, one can now quickly print out a hash sorted by key using C .say for %hash.sort : my %hash = parrot speaks your language Z 1..4; .say for %hash.sort; language4 parrot 1 speaks 2 your3 Pm
Re: r24325 - docs/Perl6/Spec
On 2008-Dec-14, at 11:21 am, Moritz Lenz wrote:
Uri Guttman wrote:
how is sort ordering specified?
Currently it is not specified, it defaults to infix:cmp. If you
can suggest a non-confusing way to specify both a transformation
closure and a comparison method, please go ahead.
how does it know to do string vs numeric sorting?
infix:cmp does numeric comparison if both operands are numbers,
and string comparison otherwise.
Cmp (like eqv) depends on the particular type, so to sort a
certain way, you should need only to coerce the values to the right
type:
@stuff.sort { .Num } # numerically
@stuff.sort { ~ .name.uc } # stringwise
@stuff.sort { Foo(%x{$_}) } # foo-wise
I don't know what cmp returns for two values of different types.
(Failure?)
-David
Re: r24325 - docs/Perl6/Spec
infix:cmp does numeric comparison if both operands are numbers, and
string comparison otherwise.
That is a bit of an oversimplification.
Cmp (like eqv) depends on the particular type, so to sort a certain
way, you should need only to coerce the values to the right type:
@stuff.sort { .Num } # numerically
@stuff.sort { ~ .name.uc } # stringwise
@stuff.sort { Foo(%x{$_}) } # foo-wise
I don't know what cmp returns for two values of different types.
(Failure?)
Any type may define infix:cmp however it likes for two arguments of
its own type. It may also define multis with other types that define
desirable coercions. The infix:cmp:(Any,Any) routine is what would
be providing the default string coercion, so it would succeed for
any two different types that match Any and have string coercions.
Outside of Any are the Object and Junction types; I suppose cmp can
thread on junctions, but trying to sort junctions might well result
in aberrant behavior, especially if we choose a sort algorithm that
coredumps on circular ordering relations. :)
Larry
Re: r24325 - docs/Perl6/Spec
LW == Larry Wall la...@wall.org writes: infix:cmp does numeric comparison if both operands are numbers, and string comparison otherwise. LW That is a bit of an oversimplification. LW Any type may define infix:cmp however it likes for two arguments of LW its own type. It may also define multis with other types that define LW desirable coercions. The infix:cmp:(Any,Any) routine is what would LW be providing the default string coercion, so it would succeed for LW any two different types that match Any and have string coercions. LW Outside of Any are the Object and Junction types; I suppose cmp can LW thread on junctions, but trying to sort junctions might well result LW in aberrant behavior, especially if we choose a sort algorithm that LW coredumps on circular ordering relations. :) this means cmp still does a string compare as long as it can coerce its args to strings. this means the shorter sort ideas being bandied about still have a major weakness - specifying the sort comparison. you can default to string like p5 sort which is fine. but how do you pass in =? or handle multiple keys with different comparison ops? this is why damian and i agree that a key description style works best for a sorter. the short versions i have seen are useful for string sorts of a single key. there are plenty of uses for that and those would be a good short cut. but there still needs to be a full sort signature of the kind damian proposed and we have both built in different modules. there is plenty to steal from there so don't go reinventing this wheel just yet. :) thanx, uri -- Uri Guttman -- u...@stemsystems.com http://www.sysarch.com -- - Perl Code Review , Architecture, Development, Training, Support -- - Free Perl Training --- http://perlhunter.com/college.html - - Gourmet Hot Cocoa Mix http://bestfriendscocoa.com -
Re: r24325 - docs/Perl6/Spec
Uri Guttman wrote: LW == Larry Wall la...@wall.org writes: infix:cmp does numeric comparison if both operands are numbers, and string comparison otherwise. LW That is a bit of an oversimplification. LW Any type may define infix:cmp however it likes for two arguments of LW its own type. It may also define multis with other types that define LW desirable coercions. The infix:cmp:(Any,Any) routine is what would LW be providing the default string coercion, so it would succeed for LW any two different types that match Any and have string coercions. LW Outside of Any are the Object and Junction types; I suppose cmp can LW thread on junctions, but trying to sort junctions might well result LW in aberrant behavior, especially if we choose a sort algorithm that LW coredumps on circular ordering relations. :) this means cmp still does a string compare as long as it can coerce its args to strings. ... and as long as no other multis are specified. I know at least of infix:cmp(Num $a, Num $b) (which does the same as Perl 5's =) and infix:cmp(Pair $a, Pair $b) (which does $a.key cmp $a.key || $a.value cmp $b.value), so numbers and pairs DWIM. Likewise sorting of AoAs is specified to first sort on the first items, then on the seconds etc. Cheers, Moritz
Re: r24325 - docs/Perl6/Spec
On Mon, Dec 15, 2008 at 5:41 PM, Moritz Lenz mor...@faui2k3.org wrote: I know at least of infix:cmp(Num $a, Num $b) (which does the same as Perl 5's =) and infix:cmp(Pair $a, Pair $b) (which does $a.key cmp $a.key || $a.value cmp $b.value), so numbers and pairs DWIM. Hm. Rakudo doesn't let me cmp pairs at all currently: (a = 2) cmp (a = 10) Multiple Dispatch: No suitable candidate found for 'cmp', with signature 'PP-I' Pugs DWIMs with numbers and string-valued pairs, but it looks like num-valued pairs get their values stringified: pugs 2 cmp 10 -1 pugs (a = 2) cmp (a = 10) 1 -- Mark J. Reed markjr...@gmail.com
Re: r24325 - docs/Perl6/Spec
Uri Guttman wrote: p == pugs-commits pugs-comm...@feather.perl6.nl writes: p This document attempts to document the list of builtin functions in Perl 6. p It assumes familiarity with Perl 5 and prior synopses. p @@ -870,6 +870,10 @@ p comparisons. C@by differs from C$by in that each criterion is p applied, in order, until a non-zero (tie) result is achieved. p +If C$by is a code object of arity zero or one, it is applied on each item p +of C@values, and C@values is sorted by comparing the result values with p +C infix:cmp (Schwartzian Transform). p + the ST is a specific implementation of this optimization. the concept is caching key extractions and expressions so they become O(N) and not O(N log N) which saves tons of cpu in larger complex sorts. but how the caching is done is really independent of the sort API/signature. as perl6 synopses aren't supposed to discuss implementation (they are language specs) calling it the schwartzian transform is somewhat out of place. I agree. As I wrote in the commit message, feel free to improve the wording - the specs are open for hacking, especially S29, which is in draft status. and some other questions: and how does that style handle multiple keys? What do you mean? The comparison is carried out on the return values of the closure. how is sort ordering specified? Currently it is not specified, it defaults to infix:cmp. If you can suggest a non-confusing way to specify both a transformation closure and a comparison method, please go ahead. how does it know to do string vs numeric sorting? infix:cmp does numeric comparison if both operands are numbers, and string comparison otherwise. damian's Perl6::Sort and my Sort::Maker address those issues but this SIG short cut doesn't (yet). also Sort::Maker generates sorts in 4 styles which may be of use to any implementors of perl6's sort. and it has an old (prize winner at TPC4) article on this topic that may be of some interest. and it only won a technical award because damian withdrew as he was the winner the previous two years in a row! :) I'll take a look. Cheers, Moritz
r24325 - docs/Perl6/Spec
Author: moritz Date: 2008-12-13 10:32:15 +0100 (Sat, 13 Dec 2008) New Revision: 24325 Modified: docs/Perl6/Spec/S29-functions.pod Log: [S29] List.sort with a unary or nullary code object does a Schwartzian Transform. (Feel free to improve the wording) Modified: docs/Perl6/Spec/S29-functions.pod === --- docs/Perl6/Spec/S29-functions.pod 2008-12-13 00:57:48 UTC (rev 24324) +++ docs/Perl6/Spec/S29-functions.pod 2008-12-13 09:32:15 UTC (rev 24325) @@ -13,8 +13,8 @@ Mark Stosberg m...@summersault.com Carl Mäsak cma...@gmail.com Date: 12 Mar 2005 - Last Modified: 19 Nov 2008 - Version: 30 + Last Modified: 13 Dec 2008 + Version: 31 This document attempts to document the list of builtin functions in Perl 6. It assumes familiarity with Perl 5 and prior synopses. @@ -870,6 +870,10 @@ comparisons. C@by differs from C$by in that each criterion is applied, in order, until a non-zero (tie) result is achieved. +If C$by is a code object of arity zero or one, it is applied on each item +of C@values, and C@values is sorted by comparing the result values with +C infix:cmp (Schwartzian Transform). + COrdering is as described in LType Declarations. Any COrdering may receive either or both of the mixins Cdescending and Ccanon(Code $how) to reverse the order of sort, or
Re: r24325 - docs/Perl6/Spec
p == pugs-commits pugs-comm...@feather.perl6.nl writes: p This document attempts to document the list of builtin functions in Perl 6. p It assumes familiarity with Perl 5 and prior synopses. p @@ -870,6 +870,10 @@ p comparisons. C@by differs from C$by in that each criterion is p applied, in order, until a non-zero (tie) result is achieved. p +If C$by is a code object of arity zero or one, it is applied on each item p +of C@values, and C@values is sorted by comparing the result values with p +C infix:cmp (Schwartzian Transform). p + the ST is a specific implementation of this optimization. the concept is caching key extractions and expressions so they become O(N) and not O(N log N) which saves tons of cpu in larger complex sorts. but how the caching is done is really independent of the sort API/signature. as perl6 synopses aren't supposed to discuss implementation (they are language specs) calling it the schwartzian transform is somewhat out of place. the ST caches the extracted keys in arrays but the GRT caches them in a single byte string which can be even faster. all the api/sig is doing is removing the redundant key extract code for both $a and $b. so say that the sort sig is easier to use for simple sorts as you don't need to express the extract code on $a/$b but it is implied to do it given the sort code block. and some other questions: and how does that style handle multiple keys? how is sort ordering specified? how does it know to do string vs numeric sorting? damian's Perl6::Sort and my Sort::Maker address those issues but this SIG short cut doesn't (yet). also Sort::Maker generates sorts in 4 styles which may be of use to any implementors of perl6's sort. and it has an old (prize winner at TPC4) article on this topic that may be of some interest. and it only won a technical award because damian withdrew as he was the winner the previous two years in a row! :) thanx, uri -- Uri Guttman -- u...@stemsystems.com http://www.sysarch.com -- - Perl Code Review , Architecture, Development, Training, Support -- - Free Perl Training --- http://perlhunter.com/college.html - - Gourmet Hot Cocoa Mix http://bestfriendscocoa.com -
