Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 04:34:22PM -0600, Jarkko Hietaniemi wrote: Of course. So how is the ST justified when you simply want to sort by length? I.e., why is this not sufficient: Those of the School of Maniacal Optimization may prefer calling length() only O(N) times, instead of O(N log N) times. Yeah, a weak argument, but then again, I didn't claim length() as such being the prime user of ST. Oops. Maybe it wasn't the best example. Ah, I think I can weasel my way out of this: now we have UTF8 strings, it's possible that calling length() on a string is an O(N) process instead of a simple lookup in the SV. (Hmm. Perhaps xpv should have had an xpv_utf8len field.) -- It's 106 miles from Birmingham, we've got an eighth of a tank of gas, half a pack of Dorritos, it's dusk, and we're wearing contacts. - Malcolm Ray
Re: Schwartzian Transform
Dan Sugalski [EMAIL PROTECTED] writes:
At 09:26 AM 3/27/2001 -0800, Peter Buckingham wrote:
Dan Sugalski wrote:
At 09:50 PM 3/26/2001 -0500, James Mastros wrote:
[..]
I'd think /perl/ should complain if your comparison function isn't
idempotent (if warnings on, of course). If nothing else, it's probably an
indicator that you should be using that schwartz thang.
If you figure out how, tell me. I'd like to make arrangements to be there
for your Nobel acceptance speech. :) (This is, alas, a variant on the
halting problem, unless you're proposing perl do the memoizing *and* still
call the functions, and complain if one doesn't match the other)
not wanting to collect my nobel prize just yet, but...
could you not try a simple test (not guaranteed to be 100% accurate though),
by copying the first data element and apply it twice and then check to see
that the result of applying it once is the same as applying it twice.
Feels a little too magic to me, and awfully fragile. I'm not
comfortable doing that, though arguments to the contrary are
welcome.
There are 3 separate notions of idempotency at work here; I'm making
up their names.
1. THE MATHEMATICAL NOTION:
f(f(x)) == f(x) for all x
We don't care about that *at all* when we're sorting (we're sorting
the x's in order of their f(x)'s, with not an f(f(x)) in sight!).
I'm not going to talk about this idempotency, I just mention it
because of the incorrect analogy from linear algebra that has been
floating around.
2. "STRONG" IDEMPOTENCY: (PURE FUNCTIONS)
Saying C$a=f(x); $a=f(x) leaves the program in the same state as
just C$a=f(x). This is achieved by avoiding assignment, not
using any routines with state (I/O, PRNGs, ...) and the like.
3. "WEAK" IDEMPOTENCY: ("PURE RESULT"?)
After C$a=f(x); more_stuff(); $b=f(x) we have C$a==$b. But the
state of the program may have been changed.
Examples include any f() that does caching (or I/O for other
purposes), logging, or profiling.
If f() is memoized then it is weakly idempotent but not strongly
idempotent, since calling f(x) for the first time may change the
memoized data.
If f() is strongly idempotent then it is of course weakly
idempotent also.
(3) is enough for the sorting examples, I think. Unfortunately it's
also a lot harder to test syntactically than is (2).
So I'd like to suggest a cop-out, similar to the "let a module do the
work" argument. MJD has a module Memoize, which is very easy to use.
You can only memoize a pure function (in one of the above 2 senses;
you can always memoize (2), and you can do (3) if the semantics of it
are "good enough" for what you want to do).
So you can say
use Memoize;
# ...
memoize 'f';
@sorted = sort { my_compare(f($a),f($b)) } @unsorted
to get a lot of the effect of the S word.
Yes, I know it's not the transform (never better and often worse),
since Memoize was designed with other things in mind. But it's
probably a "good enough" solution, and has very low brain overhead.
--
Ariel Scolnicov|"GCAAGAATTGAACTGTAG"| [EMAIL PROTECTED]
Compugen Ltd. |Tel: +972-2-5713025 (Jerusalem) \ We recycle all our Hz
72 Pinhas Rosen St.|Tel: +972-3-7658117 (Main office)`-
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555http://3w.compugen.co.il/~ariels
Re: Schwartzian Transform
So you can say
use Memoize;
# ...
memoize 'f';
@sorted = sort { my_compare(f($a),f($b)) } @unsorted
to get a lot of the effect of the S word.
Yes, and of course the inline version of this technique is also
common:
@sorted = sort { my $ac = $cache{$a} ||= f($a);
my $bc = $cache{$b} ||= f($b);
my_compare($ac,$bc);
} @unsorted;
Joseph Hall calls this the 'Orcish Maneuver'.
However (I don't know who suggested this, but:)
I'd think /perl/ should complain if your comparison function isn't
idempotent (if warnings on, of course). If nothing else, it's probably an
indicator that you should be using that schwartz thang.
I have to agree with whoever followed up that this is a really dumb
idea. It reminds me of the time I was teaching the regex class at
TPC3, and I explained how the /o in
/$foo/o
represents a promise to Perl that $foo will never change, so Perl can
skip the operation of checking to see if it has changed every time the
match is performed. Then there was a question from someone in the
audience, asking if Perl would emit a warning if $foo changed.
On the other side of the argument, however, I should mention that I've
planned for a long time to write a Sort::Test module which *would*
check to make sure the comparator function behaved properly, and would
report problems. When you use the module, it would make all your
sorts run really slowly, but you would get a warning if your
comparator was bad.
Idempotency is not the important thing here. The *important* property
that the comparator needs, and the one that bad comparators usually
lack is
if my_compare(a,b) 0, and
my_compare(b,c) 0, then it should also be the case that
my_compare(a,c) 0
for all keys a, b, and c.
Sort::Test would run a quadratic sort such as a bubble sort, and make
sure that this essential condition held true. Note in particular that
if the comparator has the form { my_compare(f(a),f(b)) }, then it does
not matter if f() is idempotent; what really matters is that
my_compare should have the property above.
I had also planned to have optional checks:
use Sort::Test 'self';
(Make sure that my_compare(a,a) == 0 for all a)
use Sort::Test 'twice';
(Make sure that my_compare(a,b) == my_compare(a,b) for all a,b)
This last is essentially the idempotency restriction again. The
reason I've never implemented this module is that in perl 5, sort()
cannot be overridden, so the usefulness seemed low; you would have to
rewrite your source code to use it. I hope this limitation is fixed
in perl 6, because it would be a cool hack.
Finally, another argument in the opposite direction yet again. It has
always seemed to me that this 'inconsistent sort comparator' thing is
a tempest in a teapot. In the past it has gotten a lot of attention
because some system libraries have a qsort() function that dumps core
if the comparator is inconsistent.
To me, this obviously indicates a defective implementation of
qsort(). If the sort function dumps core or otherwise detects an
inconsistent comparator, it is obviously functioning suboptimally. An
optimal sort will not notice that the comparator is inconsistent,
because the only you can find out that the comparator is returning
inconsistent results is if you call it in a situation where you
already know what the result should be, and it returns a different
result. An optimal sort function will not call the comparator if it
already knows what the result should be!
For example, consider the property from above:
if my_compare(a,b) 0, and
my_compare(b,c) 0, then
my_compare(a,c) 0.
If the qsort() already knows that ab and bc, what is it doing
calling my_compare(a,c)? It should be able to figure that out without
the call! The fact that it dumps core if ca means that it has called
my_compare() when it didn't need to. Similarly, a qsort that dumps
core if my_compare(a,a) != 0 has obviously wasted time by calling
my_compare() at all in this case; it should *assume* that my_compare
will return 0 here.
So perhaps the best answer to the whole discussion is that if qsort()
dumps core when given an inconsistent comparator, you should replace
it with a better qsort.
Re: Schwartzian Transform
On Wed, Mar 28, 2001 at 09:13:01AM -0500, Mark-Jason Dominus wrote:
So you can say
use Memoize;
# ...
memoize 'f';
@sorted = sort { my_compare(f($a),f($b)) } @unsorted
to get a lot of the effect of the S word.
Yes, and of course the inline version of this technique is also
common:
@sorted = sort { my $ac = $cache{$a} ||= f($a);
my $bc = $cache{$b} ||= f($b);
my_compare($ac,$bc);
} @unsorted;
Joseph Hall calls this the 'Orcish Maneuver'.
That does have the (slight) disadvantage that if f(x) returns
a false value then f(x) may be called multiple times. Of course
this can be fixed by using exists. It also has the overhead of
computing the hash value of a and b on every itteration
Personally I have found the fastest sort tends to be
my @f = map { f($_) } @unsorted;
@sorted = @unsorted[ sort { $f[$a] cmp $f[$b] } 0..$#f ];
Graham.
Re: Schwartzian Transform
On Wed, Mar 28, 2001 at 09:38:59AM -0500, John Porter wrote: Mark-Jason Dominus wrote: I have to agree with whoever followed up that this is a really dumb idea. Yahbut... (See last paragraph, below). OK, I'm agreeing with MJD on this one, and it was my idea. There is no easy way to check for statelessness in all cases. In some cases you can -- sin($a) = cos($b) is obviously stateless (if $a and $b aren't magic), because it is composed only of stateless primitives. This runs afoul of the halting problem real quick. Or so I'm told, and I belive it. If the comparison (or key extraction) function is not idempotent, that is a much worse situation than simply one of degraded performance. It means the result of sort() won't be (or at least will not be guaranteed to be) sorted! My intuition says that it will either be sorted, for a simple def of sorted ($s[i] = $s[i+1]), or will take infinite time. (The "take infinite time" is, I assume, the one that made things dump core.) if my_compare(a,b) 0, and my_compare(b,c) 0, then it should also be the case that my_compare(a,c) 0 Hm. We could call that "relative idempotency", I suppose. I'd go with "transitive", since this is a property of the comparator, not the extractor. If you seperate the comparator and the extractor(s), then the comparator must be transitive, and the extractors must be internaly stateless. But, aaui, it is not a question of the comparison function being idempotent, but the key extraction function being so. aaui? Hm. Let's define some terms like "idempotency". These are also my (current) ideas for sub attributes. Stateless: The function neither depends on state, nor modifies it. This makes it a pure (IE mathematical) function. f(a) == f(a), and there is no side-effect. sin() is stateless. This means the function is memonizeable. Internaly stateless: f(a) == f(a), but there might be sideefects that do not effect the return value. printf is internaly stateless (ignoring linenoize vars). This is the essencial property of key extractors. Note that all stateless functions are internaly stateless. Transitive: if my_compare(a,b) 0, and my_compare(b,c) 0, then it should also be the case that my_compare(a,c) 0 I can't define it better then that. (Though there's more to it then that). Note that only the sign of the answer is gaurnteed, so it doesn't even have to be internaly stateless -- but it probably doesn't make sense for it not to be. Give the braindead no head. You might want to change that to "heed". -=- James Mastros -- The most beautiful thing we can experience is the mysterious. It is the source of all true art and science. He to whom this emotion is a stranger, who can no longer pause to wonder and stand wrapt in awe, is as good as dead. -=- Albert Einstein AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
Re: Schwartzian Transform
James Mastros wrote: This runs afoul of the halting problem real quick. That would be taking the entirely wrong approach. All you'd need to do is check the return values from multiple calls with the same arguments. As long as they appear idempotent, that's all you care about. My intuition says that it will either be sorted, for a simple def of sorted ($s[i] = $s[i+1]), or will take infinite time. (The "take infinite time" is, I assume, the one that made things dump core.) Well, your intuition is not serving you well. You're mistaken on both counts. Hm. We could call that "relative idempotency", I suppose. I'd go with "transitive", since this is a property of the comparator, not the extractor. It's relative, because while the return values doen't need to be exactly the same each time, they only need to have the same signum(difference()). If you seperate the comparator and the extractor(s), then the comparator must be transitive, and the extractors must be internaly stateless. Must be? I think not. Give the braindead no head. You might want to change that to "heed". I definitely do not. The whole reason I put it in my .sig is because I like the way it sounds. If you find it offensive, well, I'll have a new one soon. -- John Porter
Re: Schwartzian Transform
Simon Cozens [EMAIL PROTECTED] writes:
On Mon, Mar 26, 2001 at 10:50:09AM -0500, Uri Guttman wrote:
SC it? That is, @s = sort { f($a) = f($b) } @t
because that would require the PSI::ESP module which isn't working
yet. how would perl intuit exactly the relationship between the records
and the keys extraction and comparison? the ST defines that by the first
map and the comparison callback. just providing the comparison would
entail perl parsing an arbitrarily complex piece of code and then
autognerating the map that would produce an anon array that fits it. not
a simple task.
No, it wouldn't, don't be silly. The ST can always be generalized to
ST(data, func, compare) =
map { $_-[0] } sort { compare($a-[1], $b-[1]) } map { [$_, f($_)] } data
In fact, you can implement it in LISP just like that:
(defun Schwartzian (list func compare)
(mapcar
(lambda (x) (car x))
(sort
(mapcar
(lambda (x) (cons x (funcall func x)))
list
)
(lambda (x y) (funcall compare (cdr x) (cdr y)))
)
)
)
So can you write that in perl5 rather than LISP?
If not what does perl6 need so we can write it in perl6.
sub Schwartzian
{
...
}
Do you see any ESP there? Do you see any parsing of arbitrary pieces of
code? No, me neither.
--
Nick Ing-Simmons [EMAIL PROTECTED]
Via, but not speaking for: Texas Instruments Ltd.
Re: Schwartzian Transform
At 07:37 PM 3/26/2001 -0800, Russ Allbery wrote: Dan Sugalski [EMAIL PROTECTED] writes: You're ignoring side-effects. The tied data may well be returned the same every time it's accessed, but that doesn't mean that things aren't happening behind the scenes. What if we were tracking the number of times a scalar/hash/array was accessed? Memoizing would kill that. Hm. I don't really understand why this would be significant unless you're actually benchmarking Perl's sort. Unless you care about the performance of Perl's sort algorithm, the number of times each element is accessed in a sort is *already* indeterminate, being a function of the (hidden) sort implementation, and will vary a lot depending on how ordered the data already is. The counting thing was just an example. The point was that someone could do something with the function calls or FETCHes on tied data. We don't currently have any places where we explicitly won't call a function or FETCH on access. (Or a STORE for that matter, since there are a bunch of places where stores to variables could be otherwise optimized away) It's not that I don't mind saying "sort will memoize and may fetch your data only once", it's just that we have no current precedent. Dan --"it's like this"--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Schwartzian Transform
Dan Sugalski wrote: At 09:50 PM 3/26/2001 -0500, James Mastros wrote: [..] I'd think /perl/ should complain if your comparison function isn't idempotent (if warnings on, of course). If nothing else, it's probably an indicator that you should be using that schwartz thang. If you figure out how, tell me. I'd like to make arrangements to be there for your Nobel acceptance speech. :) (This is, alas, a variant on the halting problem, unless you're proposing perl do the memoizing *and* still call the functions, and complain if one doesn't match the other) not wanting to collect my nobel prize just yet, but... could you not try a simple test (not guaranteed to be 100% accurate though), by copying the first data element and apply it twice and then check to see that the result of applying it once is the same as applying it twice. Ideally you could do they typical matrix type thing (getting technical again :) I x A = I x A x A A = A^2 So it would be easy if we could have an identity data element on hand, but even if we don't it is pretty unlikely that the data element will special enough to make the above true (substitute the data element for I). just some early morning dribble, peter
Re: Schwartzian Transform
At 09:26 AM 3/27/2001 -0800, Peter Buckingham wrote: Dan Sugalski wrote: At 09:50 PM 3/26/2001 -0500, James Mastros wrote: [..] I'd think /perl/ should complain if your comparison function isn't idempotent (if warnings on, of course). If nothing else, it's probably an indicator that you should be using that schwartz thang. If you figure out how, tell me. I'd like to make arrangements to be there for your Nobel acceptance speech. :) (This is, alas, a variant on the halting problem, unless you're proposing perl do the memoizing *and* still call the functions, and complain if one doesn't match the other) not wanting to collect my nobel prize just yet, but... could you not try a simple test (not guaranteed to be 100% accurate though), by copying the first data element and apply it twice and then check to see that the result of applying it once is the same as applying it twice. Feels a little too magic to me, and awfully fragile. I'm not comfortable doing that, though arguments to the contrary are welcome. Dan --"it's like this"--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Schwartzian Transform
could you not try a simple test (not guaranteed to be 100% accurate though), by copying the first data element and apply it twice and then check to see that the result of applying it once is the same as applying it twice. Feels a little too magic to me, and awfully fragile. I'm not comfortable doing that, though arguments to the contrary are welcome. I agree that it isn't great, but I don't agree that it's really fragile (although that may be difficult to prove conclusively). Take an earlier example: (rand($x) = rand($y)) I suspect that the chances of rand($x) == rand(rand($x)) would be less than 1%. I would think that if it is different that you just raise a warning anyway rather than doing anything special. There may actually be a case where someone wants to have the side-effects (not that i can think of a reason immediately off hand). To be even handed an obvious counter-example is if the first data element is say 1: squared(1) == squared(squared(1)) but clearly this is not an idempotent function. but the obvious question is if it isn't an idempotent function what do we do? do we abort? perhaps the real question is not whether we can require idempotency but what are we trying to achieve with it --- there may be another way :) peter
Re: Schwartzian Transform
Peter Buckingham wrote: but the obvious question is if it isn't an idempotent function what do we do? do we abort? perhaps the real question is not whether we can require idempotency but what are we trying to achieve with it --- there may be another way :) It is easy enough to test if the function ever fails idempotency. And it is also easy to decide we'll chuck a warning when it does. The REAL issue is whether we really want to test for idempotency. Sure, it's easy, but it is not cheap. Do we want to pay the cost? It requires caching the values from every call, but STILL calling the function every time. You know, if we're going to cache the result, we may as well use it, i.e. memoize. Unless, of course, the optimizer can't assume the function has no side-effects. -- John Porter Give the braindead no head.
Re: Schwartzian Transform
John Porter wrote: And I don't like the name ":constant", it smacks too much of OO. I'd hope we would come up with a better name. :function ? :pure ? -- John Porter
Re: Schwartzian Transform
James Mastros wrote:
[..]
f("+123,456")=123456
f(f("+123,456))=123456
The functon is not idempotent. Even if you checked f(x)==x (function is the
identity), an input of "123456" would work.
just a comment on this, we are talking about sorting which would generally
mean that the function would have to output a number, which would make the
behaviour of the functions much more maths-like. the above function would
probably not be used in a sort routine i think :)
I agree with john's later message that the real issue is the optimiser which
means that having to run the function is not really an option. so this thread
is kind of irrelevant :) (sorry)
peter
Re: Schwartzian Transform
please ignore my previous message. i think that my mind was trapped in an
alternate dimension :)
peter
Peter Buckingham wrote:
James Mastros wrote:
[..]
f("+123,456")=123456
f(f("+123,456))=123456
The functon is not idempotent. Even if you checked f(x)==x (function is the
identity), an input of "123456" would work.
just a comment on this, we are talking about sorting which would generally
mean that the function would have to output a number, which would make the
behaviour of the functions much more maths-like. the above function would
probably not be used in a sort routine i think :)
I agree with john's later message that the real issue is the optimiser which
means that having to run the function is not really an option. so this thread
is kind of irrelevant :) (sorry)
peter
Re: Schwartzian Transform
Simon Cozens wrote:
On Mon, Mar 26, 2001 at 04:36:35PM -0500, Uri Guttman wrote:
SC Do you see any ESP there? Do you see any parsing of arbitrary
SC pieces of code? No, me neither.
and even creating a function to extract the key is not for beginners in
many case. most of the time i see issues with the ST is with key
extraction.
With all due respect, that's not been my experience. Even beginners know
how to do things like "length", by far the most common case for the ST.
All this talk of making the ST accessible to beginners is misguided.
It's not a core capability, it's an
optimization, and one with alternatives. If a beginner lacks the
sophistication to understand map sort
map, then their programs probably don't need anything better than sort {
$a-{'key1'}{'key2'} =
$b-{'key1'}{'key2'} }, or perhaps the orcish manuever if they are
feeling frisky. Sure, you got the
extra dereferences, but for most of programs the novice will write, it's
just one of many suboptimal
constructs they will use.
Re: Schwartzian Transform
On Tue, Mar 20, 2001 at 11:15:51PM -0500, John Porter wrote:
So you think
@s =
map { $_-[0] }
sort { $a-[1] = $b-[1] }
map { [ $_, /num:(\d+)/ ] }
@t;
would be more clearly written as
@s = schwartzian(
{
second_map = sub { $_-[0] },
the_sort= sub { $a-[1] = $b-[1] },
first_map = sub { [ $_, /num:(\d+)/ ] },
},
@t );
Why can't Perl automagically do a Schwartzian when it sees a comparison with
complicated operators or functions on each side of it?
That is, @s = sort { f($a) = f($b) } @t would Do The Right Thing.
--
What happens if a big asteroid hits the Earth? Judging from realistic
simulations involving a sledge hammer and a common laboratory frog, we
can assume it will be pretty bad. - Dave Barry
Re: Schwartzian Transform
"SC" == Simon Cozens [EMAIL PROTECTED] writes:
SC Why can't Perl automagically do a Schwartzian when it sees a
SC comparison with complicated operators or functions on each side of
SC it? That is, @s = sort { f($a) = f($b) } @t would Do The Right
SC Thing.
because that would require the PSI::ESP module which isn't working
yet. how would perl intuit exactly the relationship between the records
and the keys extraction and comparison? the ST defines that by the first
map and the comparison callback. just providing the comparison would
entail perl parsing an arbitrarily complex piece of code and then
autognerating the map that would produce an anon array that fits it. not
a simple task. if you instead defined a minilanguage that describes the
keys and how to extract them, you could generate the extraction and
comaprison code from that. that is the gist of the (currently shelved)
Sort::Records.
uri
--
Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com
SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting
The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books
The Best Search Engine on the Net -- http://www.northernlight.com
Re: Schwartzian Transform
At 10:50 AM 3/26/2001 -0500, Uri Guttman wrote:
"SC" == Simon Cozens [EMAIL PROTECTED] writes:
SC Why can't Perl automagically do a Schwartzian when it sees a
SC comparison with complicated operators or functions on each side of
SC it? That is, @s = sort { f($a) = f($b) } @t would Do The Right
SC Thing.
because that would require the PSI::ESP module which isn't working
yet. how would perl intuit exactly the relationship between the records
and the keys extraction and comparison?
I'm kinda puzzled by the focus on Schwartzian when I thought the GRT was
demonstrated to be better. Anyway, all we need is a syntax for specifying
an extraction function and whether the comparison is string or numeric. If
the parser can be persuaded to accept an array ref instead of a block, how
about
sort [ '=' = \f ] @t
doing The Right Thing? I guess you could also pragmatize it if you wanted
a particular transform:
use sort qw(schwartzian);
Someone could probably turn this into "use the schwartz".
Re: Schwartzian Transform
"PS" == Peter Scott [EMAIL PROTECTED] writes: PS I'm kinda puzzled by the focus on Schwartzian when I thought the PS GRT was demonstrated to be better. Anyway, all we need is a PS syntax for specifying an extraction function and whether the PS comparison is string or numeric. If the parser can be persuaded PS to accept an array ref instead of a block, how about PS sort [ '=' = \f ] @t how about multikey support? sort ordering (ascending, descending) which is also per key, etc. you could have a list of those pairs to deal with multikeys, but you need a sort order flag somewhere. but if that is all you have, you could do this with a simple module and it doesn't have to be in the perl language. just loop over the list of pairs (triplets?) and generate a map that calls each function which builds up the list of keys with the original record in [0]. then build up code that does a sequence of compares with $a-[$n], etc for each of the keys. then eval the whole mess and pray. :) and when using the GRT you need to know if the integers are signed/unsigned if you pack them with the 'N' long format. if you use sprintf, you need to know the maximum digit count of all the key values. this is one win of the ST over the GRT, you don't need to know as much about the key as perl will do the comparisons right with just cmp and =. you still need sort order and multikey support. otherwise you don't gain so much. uri -- Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books The Best Search Engine on the Net -- http://www.northernlight.com
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 10:50:09AM -0500, Uri Guttman wrote:
SC it? That is, @s = sort { f($a) = f($b) } @t
because that would require the PSI::ESP module which isn't working
yet. how would perl intuit exactly the relationship between the records
and the keys extraction and comparison? the ST defines that by the first
map and the comparison callback. just providing the comparison would
entail perl parsing an arbitrarily complex piece of code and then
autognerating the map that would produce an anon array that fits it. not
a simple task.
No, it wouldn't, don't be silly. The ST can always be generalized to
ST(data, func, compare) =
map { $_-[0] } sort { compare($a-[1], $b-[1]) } map { [$_, f($_)] } data
In fact, you can implement it in LISP just like that:
(defun Schwartzian (list func compare)
(mapcar
(lambda (x) (car x))
(sort
(mapcar
(lambda (x) (cons x (funcall func x)))
list
)
(lambda (x y) (funcall compare (cdr x) (cdr y)))
)
)
)
Do you see any ESP there? Do you see any parsing of arbitrary pieces of
code? No, me neither.
--
SM is fun. ADSM is not.
"Safe, Sane, Consensual"... three words that cannot used to describe
ADSM.
- Graham Reed, sdm.
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 08:25:17AM -0800, Peter Scott wrote: I'm kinda puzzled by the focus on Schwartzian when I thought the GRT was demonstrated to be better. Because the insert name here transform is a specialized case of the schwartzian transform where the default sort is sufficient. Address the issues with the general case, and the specialized case is handled as well. Z.
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 10:50:09AM -0500, Uri Guttman wrote:
"SC" == Simon Cozens [EMAIL PROTECTED] writes:
SC Why can't Perl automagically do a Schwartzian when it sees a
SC comparison with complicated operators or functions on each side of
SC it? That is, @s = sort { f($a) = f($b) } @t would Do The Right
SC Thing.
because that would require the PSI::ESP module which isn't working
yet.
Not at all. Simon's example looks like a simple case of memoization.
The cache only needs to be maintained for the duration of the sort,
and it alleviates the need for complicated map{} operations.
how would perl intuit exactly the relationship between the records
and the keys extraction and comparison?
The key extraction is done with f(), and the comparison is done
with cached values of f().
Z.
Re: Schwartzian Transform
At 03:23 PM 3/26/2001 -0500, Adam Turoff wrote:
On Mon, Mar 26, 2001 at 10:50:09AM -0500, Uri Guttman wrote:
"SC" == Simon Cozens [EMAIL PROTECTED] writes:
SC Why can't Perl automagically do a Schwartzian when it sees a
SC comparison with complicated operators or functions on each side of
SC it? That is, @s = sort { f($a) = f($b) } @t would Do The Right
SC Thing.
because that would require the PSI::ESP module which isn't working
yet.
Not at all. Simon's example looks like a simple case of memoization.
The cache only needs to be maintained for the duration of the sort,
and it alleviates the need for complicated map{} operations.
The only issue there is whether memoization is appropriate. It could be
argued that it isn't (it certainly isn't with perl 5) though I for one
wouldn't mind being able to more aggressively assume that data was
semi-constant... (Imagine returning tied data from a function loaded in via
do(). Imagine the optimizer. Imagine Dan's brain popping out of his head
and hiding behind the bookcase)
Dan
--"it's like this"---
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 03:36:08PM -0500, Dan Sugalski wrote:
The only issue there is whether memoization is appropriate. It could be
argued that it isn't (it certainly isn't with perl 5)
Hm. I don't see a linguistic reason why it isn't with perl5. Unless the
comparisign function as a whole is stable (IE {f(a) = f(b)}, the sort
function is documented as being undefined.
The only way f(a) can not be stable and f(a) = f(b) can be is somthing of
a corner case. In fact, it's a lot of a corner case.
though I for one
wouldn't mind being able to more aggressively assume that data was
semi-constant...
Well, you can. Unless it has magic (and more specificly, scalar get magic).
(Imagine returning tied data from a function loaded in via
do(). Imagine the optimizer. Imagine Dan's brain popping out of his head
and hiding behind the bookcase)
That's a really wierd image. Twisted, even.
-=- James Mastros
--
The most beautiful thing we can experience is the mysterious. It is the
source of all true art and science. He to whom this emotion is a stranger,
who can no longer pause to wonder and stand wrapt in awe, is as good as dead.
-=- Albert Einstein
AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
Re: Schwartzian Transform
Dan Sugalski wrote: The only issue there is whether memoization is appropriate. It could be argued that it isn't (it certainly isn't with perl 5) though I for one wouldn't mind being able to more aggressively assume that data was semi-constant... The :idempotent attribute for subs? -- John Porter Useless use of time in void context.
Re: Schwartzian Transform
"SC" == Simon Cozens [EMAIL PROTECTED] writes:
SC No, it wouldn't, don't be silly. The ST can always be generalized to
SC ST(data, func, compare) =
SC map { $_-[0] } sort { compare($a-[1], $b-[1]) } map { [$_, f($_)] } data
and i don't see multiple keys or sort order selection per key. and read
my other post about how that could be partly done but it belongs in a
module instead of a builtin.
SC Do you see any ESP there? Do you see any parsing of arbitrary
SC pieces of code? No, me neither.
and even creating a function to extract the key is not for beginners in
many case. most of the time i see issues with the ST is with key
extraction.
uri
--
Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com
SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting
The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books
The Best Search Engine on the Net -- http://www.northernlight.com
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 04:36:35PM -0500, Uri Guttman wrote: SC Do you see any ESP there? Do you see any parsing of arbitrary SC pieces of code? No, me neither. and even creating a function to extract the key is not for beginners in many case. most of the time i see issues with the ST is with key extraction. With all due respect, that's not been my experience. Even beginners know how to do things like "length", by far the most common case for the ST. -- "He was a modest, good-humored boy. It was Oxford that made him insufferable."
Re: Schwartzian Transform
"SC" == Simon Cozens [EMAIL PROTECTED] writes: SC On Mon, Mar 26, 2001 at 04:36:35PM -0500, Uri Guttman wrote: and even creating a function to extract the key is not for beginners in many case. most of the time i see issues with the ST is with key extraction. SC With all due respect, that's not been my experience. Even SC beginners know how to do things like "length", by far the most SC common case for the ST. well, you must be hanging around smart newbies. :) i can't count the number of times i have seen in c.l.p.misc the question "how can i find the length of a string?" we even have a running gag calling that and similar ones "self answering questions". still, a module which takes the same type of arguments and supports multiple keys would be a better choice than a new builtin IMO. the operator you propose is more complex than almost any other and it just serves to make one algorithmic trick have a better syntax. but a module can do the same thing. larry has the final say here and i feel he won't want to burden the language with this just for a small gain that can be done in a module. uri -- Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books The Best Search Engine on the Net -- http://www.northernlight.com
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 04:54:51PM -0500, Uri Guttman wrote: well, you must be hanging around smart newbies. :) No, I just learn 'em right. :) -- The Blit is a nice terminal, but it runs emacs.
Re: Schwartzian Transform
Simon Cozens wrote:
With all due respect, that's not been my experience. Even beginners know
how to do things like "length", by far the most common case for the ST.
You must be kidding. Sorting a list of strings by length is more
common that, say, sorting them numerically by some embedded number?
I don't think so.
Besides, simply sorting strings by length doesn't require ST.
The ST applies when you want to sort by one or more embedded "fields".
So, sorting by length of an embedded field is the most common case?
I can honestly say that I have never done this, seen it, recommended
it, or seen it recommended (though I admit it must come up from time
to time):
map { $_-[0] }
sort { $a-[1] = $b-[1] }
map { my($s) = /X(.*?)Y/; [ $_, length($s) ] }
@items
--
John Porter
Useless use of time in void context.
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 05:17:38PM -0500, John Porter wrote: Simon Cozens wrote: With all due respect, that's not been my experience. Even beginners know how to do things like "length", by far the most common case for the ST. You must be kidding. Sorting a list of strings by length is more common that, say, sorting them numerically by some embedded number? I don't think so. Besides, simply sorting strings by length doesn't require ST. The ST applies when you want to sort by one or more embedded "fields". Huh? ST (or GR) applies to any situation where you your sort comparator function isn't directly expressible with (Perl) primitives, and worthwhile it is (like Yoda feel I) when the cost of converting the keys (so that the primitives can again be employed) begins to dominate the overall cost of sort(). -- $jhi++; # http://www.iki.fi/jhi/ # There is this special biologist word we use for 'stable'. # It is 'dead'. -- Jack Cohen
Re: Schwartzian Transform
Jarkko Hietaniemi wrote:
ST (or GR) applies to any situation where you your sort
comparator function isn't directly expressible with (Perl) primitives,
and worthwhile it is (like Yoda feel I) when the cost of converting
the keys (so that the primitives can again be employed) begins to
dominate the overall cost of sort().
Of course. So how is the ST justified when you simply want to
sort by length? I.e., why is this not sufficient:
sort { length($a) = length($b) } # I see no ST here.
And this was alleged to be the most common case for ST.
--
John Porter
Useless use of time in void context.
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 05:29:24PM -0500, John Porter wrote:
Jarkko Hietaniemi wrote:
ST (or GR) applies to any situation where you your sort
comparator function isn't directly expressible with (Perl) primitives,
and worthwhile it is (like Yoda feel I) when the cost of converting
the keys (so that the primitives can again be employed) begins to
dominate the overall cost of sort().
Of course. So how is the ST justified when you simply want to
sort by length? I.e., why is this not sufficient:
Those of the School of Maniacal Optimization may prefer calling
length() only O(N) times, instead of O(N log N) times. Yeah, a weak
argument, but then again, I didn't claim length() as such being the
prime user of ST. I just jumped at your "fields" description, which
sounded odd to me. There need not be "fields" by any stretch of the
term. It's all about reduction to primitive-comparable and the
relative cost of it.
sort { length($a) = length($b) } # I see no ST here.
And this was alleged to be the most common case for ST.
--
$jhi++; # http://www.iki.fi/jhi/
# There is this special biologist word we use for 'stable'.
# It is 'dead'. -- Jack Cohen
Re: Schwartzian Transform
Jarkko Hietaniemi wrote: It's all about reduction to primitive-comparable and the relative cost of it. You're right. Extraction of fields is only one example. (But it's illustrative, no?) -- John Porter Useless use of time in void context.
Re: Schwartzian Transform
At 04:33 PM 3/26/2001 -0500, John Porter wrote: Dan Sugalski wrote: The only issue there is whether memoization is appropriate. It could be argued that it isn't (it certainly isn't with perl 5) though I for one wouldn't mind being able to more aggressively assume that data was semi-constant... The :idempotent attribute for subs? Only trustable if there are no do, eval, or require calls past BEGIN time, and we don't see any redefining subroutines. If we disallow changing the attributes on subs at runtime, or explicitly allow the optimizer to optimize away access to active data, then things are different and we're fine. Dan --"it's like this"--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Schwartzian Transform
At 06:11 PM 3/26/2001 -0500, John Porter wrote:
Trond Michelsen wrote:
I realize that memoization isn't something you want to do on functions
that may return different results with the same input. However I'm a bit
curious of when these functions are useful in sort(),
...
sort {rand($a) = rand($b)} @nums;
Right.
Will the above generate a more random list than this?
No, it will generate a more crashed perl.
I thought we fixed that particular core dump.
Dan
--"it's like this"---
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
Re: Schwartzian Transform
At 04:04 PM 3/26/2001 -0500, James Mastros wrote:
On Mon, Mar 26, 2001 at 03:36:08PM -0500, Dan Sugalski wrote:
The only issue there is whether memoization is appropriate. It could be
argued that it isn't (it certainly isn't with perl 5)
Hm. I don't see a linguistic reason why it isn't with perl5. Unless the
comparisign function as a whole is stable (IE {f(a) = f(b)}, the sort
function is documented as being undefined.
The only way f(a) can not be stable and f(a) = f(b) can be is somthing of
a corner case. In fact, it's a lot of a corner case.
You're ignoring side-effects. The tied data may well be returned the same
every time it's accessed, but that doesn't mean that things aren't
happening behind the scenes. What if we were tracking the number of times a
scalar/hash/array was accessed? Memoizing would kill that.
Whether this is sufficient argument to not allow it is a separate issue,
but that's not my call. I'd really like it to form an optimizer standpoint,
but it does cut off the possibility for some potentially interesting things
from a programmer standpoint.
though I for one
wouldn't mind being able to more aggressively assume that data was
semi-constant...
Well, you can. Unless it has magic (and more specificly, scalar get magic).
Yeah, but figuring out whether data isn't magic is rather tricky. Once a
little uncertainty comes in (Say, from AUTOLOADed subs, or from subs whose
contents we don't know at compile time because of runtime requires, or
because we really do have magic data and the potential uncertainty from it
flares out quickly) it really cuts down on what the optimizer can do.
Granted, we may just say "don't do that if you want fast code" which is OK,
but I can see the data flow analysis getting really nasty really quickly
for reasonably sized programs.
(Imagine returning tied data from a function loaded in via
do(). Imagine the optimizer. Imagine Dan's brain popping out of his head
and hiding behind the bookcase)
That's a really wierd image. Twisted, even.
Just doing my part to make the world a little more surreal...
Dan
--"it's like this"---
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
Re: Schwartzian Transform
Dan Sugalski wrote: John Porter wrote: No, it will generate a more crashed perl. I thought we fixed that particular core dump. Yes; but it's still bad. We just are more stable in the face of this badness. -- John Porter
Re: Schwartzian Transform
Dan Sugalski wrote: You're ignoring side-effects. The tied data may well be returned the same every time it's accessed, but that doesn't mean that things aren't happening behind the scenes. Like the :constant attribute on object methods in certain other languages. So, we could say, if :constant not on the sub, don't cache. As for :idempotent, I think sort() needs to assume the comparison sub is idempotent, rather than requiring such an attribute explicitly. -- John Porter Give the braindead no head.
Re: Schwartzian Transform
At 07:01 PM 3/26/2001 -0500, John Porter wrote: Dan Sugalski wrote: If we disallow changing the attributes on subs at runtime, Probably a good idea anyway, at least for a subset of attributes, such as :idempotent (or :constant). Oh, it's a fine idea, and I'm personally all for it. Anything that reduces the uncertainty the optimizer sees is fine with me. :) It is, however, Larry's call, though I can certainly rattle off the things I'd like to see as options. Dan --"it's like this"--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 05:44:43PM -0500, John Porter wrote: Jarkko Hietaniemi wrote: It's all about reduction to primitive-comparable and the relative cost of it. You're right. Extraction of fields is only one example. (But it's illustrative, no?) I like to use sorting filenames based on the file's size as an example. Nothing like throwing some disk accesses into it if slow is what you seek. -- Tad McClellan SGML consulting [EMAIL PROTECTED] Perl programming Fort Worth, Texas
Re: Schwartzian Transform
Tad McClellan wrote: Nothing like throwing some disk accesses into it if slow is what you seek. Yeah. Or web fetches! -- John Porter
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 07:31:29PM -0500, Dan Sugalski wrote: At 06:51 PM 3/26/2001 -0500, John Porter wrote: As for :idempotent, I think sort() needs to assume the comparison sub is idempotent, rather than requiring such an attribute explicitly. Assuming idempotency's fine, though I don't know that I'd go so far as to require it. I certainly wouldn't complain, though. I'd think /perl/ should complain if your comparison function isn't idempotent (if warnings on, of course). If nothing else, it's probably an indicator that you should be using that schwartz thang. -=- James Mastros -- The most beautiful thing we can experience is the mysterious. It is the source of all true art and science. He to whom this emotion is a stranger, who can no longer pause to wonder and stand wrapt in awe, is as good as dead. -=- Albert Einstein AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 06:31:22PM -0500, Dan Sugalski wrote: At 04:04 PM 3/26/2001 -0500, James Mastros wrote: The only way f(a) can not be stable and f(a) = f(b) can be is somthing of a corner case. In fact, it's a lot of a corner case. You're ignoring side-effects. Damm. I hate it when I miss the obvious. It's still a corner case, but not so ignorable of one. Well, you can. Unless it has magic (and more specificly, scalar get magic). Yeah, but figuring out whether data isn't magic is rather tricky. It shouldn't be, since we have to check for scalar get magic every time we get the value as a scalar anyway. Figuring out whether it is depenedent on some other thing which is magic, on the other hand, is really freeking nasty. Once a little uncertainty comes in (Say, from AUTOLOADed subs, or from subs whose contents we don't know at compile time because of runtime requires, or because we really do have magic data and the potential uncertainty from it flares out quickly) it really cuts down on what the optimizer can do. Youch. I tend to forget how "incestuous" perl is (as another message on a perl6 list said quite some time ago). I'm definatly with the guys who say we should have a :constant and a :idempotent attrib for subs, and make them unremovable. -=- James Mastros -- The most beautiful thing we can experience is the mysterious. It is the source of all true art and science. He to whom this emotion is a stranger, who can no longer pause to wonder and stand wrapt in awe, is as good as dead. -=- Albert Einstein AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
Re: Schwartzian Transform
Uri Guttman [EMAIL PROTECTED] writes:
"SC" == Simon Cozens [EMAIL PROTECTED] writes:
SC No, it wouldn't, don't be silly. The ST can always be generalized to
SC ST(data, func, compare) =
SC map { $_-[0] } sort { compare($a-[1], $b-[1]) } map { [$_, f($_)] } data
and i don't see multiple keys or sort order selection per key.
Then you need to look at f and compare a little closer, since it's in
there.
and even creating a function to extract the key is not for beginners in
many case.
Without creating a function to extract the key, you can't sort in Perl at
all. sort { $a = $b } contains two functions to extract the keys.
Functions don't have to be complicated, you know.
--
Russ Allbery ([EMAIL PROTECTED]) http://www.eyrie.org/~eagle/
Re: Schwartzian Transform
Dan Sugalski [EMAIL PROTECTED] writes: You're ignoring side-effects. The tied data may well be returned the same every time it's accessed, but that doesn't mean that things aren't happening behind the scenes. What if we were tracking the number of times a scalar/hash/array was accessed? Memoizing would kill that. Hm. I don't really understand why this would be significant unless you're actually benchmarking Perl's sort. Unless you care about the performance of Perl's sort algorithm, the number of times each element is accessed in a sort is *already* indeterminate, being a function of the (hidden) sort implementation, and will vary a lot depending on how ordered the data already is. Counting on side effects determined by the *number* of times elements are accessed during a sort sounds pretty twisted to me. I can see a few YAPHs with such properties, but I don't think we were guaranteeing that Perl 6 would be YAPH-compatible anyway. -- Russ Allbery ([EMAIL PROTECTED]) http://www.eyrie.org/~eagle/
Re: Schwartzian Transform
"RA" == Russ Allbery [EMAIL PROTECTED] writes:
RA Uri Guttman [EMAIL PROTECTED] writes:
"SC" == Simon Cozens [EMAIL PROTECTED] writes:
SC No, it wouldn't, don't be silly. The ST can always be generalized to
SC ST(data, func, compare) =
SC map { $_-[0] } sort { compare($a-[1], $b-[1]) } map { [$_, f($_)] } data
^^^ ^^^
and i don't see multiple keys or sort order selection per key.
RA Then you need to look at f and compare a little closer, since it's in
RA there.
and there is only extracted key being compared to another at the same
level, not multiple key levels. think about sorting by state and THEN
town. you can't do that with $a and $b and one f(). so you need multiple
compare ops and multiple f()'s. the point is that you have to generate
the ladder compare code as well as the calls to your f()'s.
RA Without creating a function to extract the key, you can't sort in
RA Perl at all. sort { $a = $b } contains two functions to extract
RA the keys.
huh? $a and $b are not functions but aliases the the current pair of
keys (at the primary key level). i don't seen any functions in what you
show there. you don't need a function or even an ST to sort complex
records. as other have stated here, the ST is useful to remove common
key extraction code from the compare callback.
RA Functions don't have to be complicated, you know.
but sorts can be very complex. i think we are having a 'key' meaning
overload. i am using it in form of 'state' being the first key and
'town' being the second when sorting street addresses. $a and $b are
both values from the same key, not the key itself. in the ST $a and $b
are refs to the generated anon arrays being compared. they are not the
keys values, which are in $a-[1], $a-[2], etc., with the original
record being in $a-[0].
uri
--
Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com
SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting
The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books
The Best Search Engine on the Net -- http://www.northernlight.com
Re: Schwartzian Transform
Uri Guttman [EMAIL PROTECTED] writes:
"RA" == Russ Allbery [EMAIL PROTECTED] writes:
RA Uri Guttman [EMAIL PROTECTED] writes:
map { $_-[0] } sort { compare($a-[1], $b-[1]) } map { [$_, f($_)] } data
^^^ ^^^
RA Then you need to look at f and compare a little closer, since it's in
RA there.
and there is only extracted key being compared to another at the same
level, not multiple key levels. think about sorting by state and THEN
town. you can't do that with $a and $b and one f().
Yes. You can.
Don't assume $a-[1] is a simple scalar. What prevents f() from returning
an array ref?
so you need multiple compare ops and multiple f()'s.
No, you don't.
the point is that you have to generate the ladder compare code as well
as the calls to your f()'s.
Yes, you have to write the comparison and data manipulation function for
Perl; Perl isn't going to be able to figure it out for itself. But that's
true regardless of the sorting method; you're always going to have to tell
Perl what the keys are and how to compare them.
You have to write slightly more code if you separate the extraction
function f() from the comparison function compare() since if the key
structure is complex, f() has to build a data struction that compare()
takes apart. That makes the memoizing approach superior.
RA Without creating a function to extract the key, you can't sort in
RA Perl at all. sort { $a = $b } contains two functions to extract
RA the keys.
huh? $a and $b are not functions but aliases the the current pair of
keys (at the primary key level).
Is sub { $a } a function? $a is equivalent to that. One way to look at
this is that Perl lets you simplify the function if all you need is the
basic data unit.
i don't seen any functions in what you show there. you don't need a
function or even an ST to sort complex records.
{ $a = $b } is a function. (Well, it's a code block, but the difference
is quibbling.)
My point is that writing functions isn't nearly as complicated as you make
it sound. Almost every time I write a sort, map, or grep in Perl, I write
a function.
--
Russ Allbery ([EMAIL PROTECTED]) http://www.eyrie.org/~eagle/
Re: Schwartzian Transform
"RA" == Russ Allbery [EMAIL PROTECTED] writes:
RA Uri Guttman [EMAIL PROTECTED] writes:
map { $_-[0] } sort { compare($a-[1], $b-[1]) } map { [$_, f($_)] } data
^^^ ^^^
and there is only extracted key being compared to another at the same
level, not multiple key levels. think about sorting by state and THEN
town. you can't do that with $a and $b and one f().
RA Yes. You can.
RA Don't assume $a-[1] is a simple scalar. What prevents f() from
RA returning an array ref?
i never assumed that. but your ST example above shows it like that. you
still have to do a ladder compare with $a and $b do make the ST work
with multiple keys. each one needs to be given the sort order and
compare op as well.
so you need multiple compare ops and multiple f()'s.
RA No, you don't.
yes you do. unless you use the GRT. an ST can only compare 1 key at a
time without a ladder compare. that is its major weakness.
RA Yes, you have to write the comparison and data manipulation
RA function for Perl; Perl isn't going to be able to figure it out
RA for itself. But that's true regardless of the sorting method;
RA you're always going to have to tell Perl what the keys are and how
RA to compare them.
that is my whole point of why putting this into the language is
silly. it is too open ended for amount of work perl would have to do
vs. the amount of coding you save. you save very little as you are doing
most of the work youself in the f() key extraction subs.
RA You have to write slightly more code if you separate the extraction
RA function f() from the comparison function compare() since if the key
RA structure is complex, f() has to build a data struction that compare()
RA takes apart. That makes the memoizing approach superior.
and how is this ladder compare built? f() can't return it. it has to be
real perl code in the callback block, not lists of things.
RA Without creating a function to extract the key, you can't sort in
RA Perl at all. sort { $a = $b } contains two functions to extract
RA the keys.
huh? $a and $b are not functions but aliases the the current pair of
keys (at the primary key level).
RA Is sub { $a } a function? $a is equivalent to that. One way to look at
RA this is that Perl lets you simplify the function if all you need is the
RA basic data unit.
that still doesn't answer the issue of the ladder compare and who
creates it.
i don't seen any functions in what you show there. you don't need a
function or even an ST to sort complex records.
RA My point is that writing functions isn't nearly as complicated as
RA you make it sound. Almost every time I write a sort, map, or grep
RA in Perl, I write a function.
but you don't autogenerate the code in the block. it is your code. the
supposed goal of this hypothetical builtin ST is to make it easier to
use it. i say it is not worth the effort since you have to do almost as
much work anyway. the key extraction (and possibly the ladder compare)
is still provided by you.
uri
--
Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com
SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting
The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books
The Best Search Engine on the Net -- http://www.northernlight.com
Re: Schwartzian Transform
map { $_-[0] } sort { compare($a-[1], $b-[1]) } map { [$_, f($_)] } data
Uri Guttman [EMAIL PROTECTED] writes:
i never assumed that. but your ST example above shows it like that. you
still have to do a ladder compare with $a and $b do make the ST work
with multiple keys. each one needs to be given the sort order and
compare op as well.
That's what compare() does. compare() is a Perl function. It can do
anything you want.
that is my whole point of why putting this into the language is
silly. it is too open ended for amount of work perl would have to do
vs. the amount of coding you save. you save very little as you are doing
most of the work youself in the f() key extraction subs.
The purpose served is that it's conceptually simpler to tell Perl "here's
how to extract keys and here's how to compare them; now sort this data
structure" than it is to tell Perl "convert this data structure into a
different one and then extract keys from it like follows and compare them,
then transform the structure back." The first route is closer to the way
that people are intuitively thinking. It doesn't matter to me that the
first isn't going to be that many fewer characters of Perl code than the
second. I *understand* it better.
It is true that it can be done in a module. Most things in Perl can. It
matters very little to me whether it's a standard module or built into the
language; I just think that it should be possible to tell sort to make
this sort of thing easier.
RA You have to write slightly more code if you separate the
RA extraction function f() from the comparison function compare()
RA since if the key structure is complex, f() has to build a data
RA struction that compare() takes apart. That makes the memoizing
RA approach superior.
and how is this ladder compare built?
The programmer writes it.
but you don't autogenerate the code in the block.
I haven't heard anyone talking about autogenerating everything other than
the code that wraps each element of the list in an anonymous array holding
the element and the key(s) and then extracts the key(s) for the comparison
function. That part of the code is identical in every ST that I write.
it is your code. the supposed goal of this hypothetical builtin ST is to
make it easier to use it. i say it is not worth the effort since you
have to do almost as much work anyway.
Less mental effort is the important part, not how many characters have to
be typed. I don't want to be thinking about that extra level of arrays,
and until you've written *lots* of ST's, you can't ignore it.
--
Russ Allbery ([EMAIL PROTECTED]) http://www.eyrie.org/~eagle/
Re: Schwartzian Transform
On Mon, Mar 26, 2001 at 03:36:08PM -0500, Dan Sugalski wrote:
because that would require the PSI::ESP module which isn't working
yet.
Not at all. Simon's example looks like a simple case of memoization.
The cache only needs to be maintained for the duration of the sort,
and it alleviates the need for complicated map{} operations.
The only issue there is whether memoization is appropriate. It could be
argued that it isn't (it certainly isn't with perl 5) though I for one
I realize that memoization isn't something you want to do on functions
that may return different results with the same input. However I'm a bit
curious of when these functions are useful in sort(), and in particular
when you _really_ need every comparison to be unmemoized.
sort {rand($a) = rand($b)} @nums;
Is it really desirable to get different results from rand() on every
single comparison?
Will the above generate a more random list than this?
map { $_-[0] }
sort { $a-[1] = $b-[1] }
map { [$_, rand($_)] }
@nums;
--
Trond Michelsen
Re: Schwartzian Transform
Trond Michelsen wrote:
I realize that memoization isn't something you want to do on functions
that may return different results with the same input. However I'm a bit
curious of when these functions are useful in sort(),
...
sort {rand($a) = rand($b)} @nums;
Right.
Will the above generate a more random list than this?
No, it will generate a more crashed perl.
--
John Porter
Re: Schwartzian Transform
On Thu, Mar 22, 2001 at 11:13:47PM -0500, John Porter wrote:
Brent Dax wrote:
Someone else showed a very ugly syntax with an anonymous
hash, and I was out to prove there was a prettier way to do it.
Do we want prettier? Or do we want more useful?
Perl is not exactly known for its pretty syntax.
If you have to explicitly specify both the forward and inverse transforms,
then it isn't very useful -- it's nothing more then map/sort/map. OTOH, if
you only have to specify the forward mapping, it becomes more useful. Thus,
I think the best syntax is
tsort({xform}, {compare}, @list), where the {}s are anon blocks or curried
expressions (same thing) and xform specifies the forward mapping (IE (lc
^_)) and compare specifies the comparator (IE (^_ cmp ^_)).
This would always (do the equiv to) create a LoL in the inner map, sort on
the -[0] elem, and extract the -[1] elem. Thus, it might not be as
effecent as a hand-crafted schwartzian, but will be at least as efficent as
a naieve straight sort (except in pathalogical cases, like tsort((^_),
(^_=^_), @list)).
-=- James Mastros
--
The most beautiful thing we can experience is the mysterious. It is the
source of all true art and science. He to whom this emotion is a stranger,
who can no longer pause to wonder and stand wrapt in awe, is as good as dead.
-=- Albert Einstein
AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
Re: Schwartzian Transform
i have to put my 2 cents in...
after reading all the discussion so far about the Schwartz,
i feel that map{} sort map{} is perfect in it's syntax.
if you code and understand Perl (i've seen situations where
these aren't always both happening at the time) and knowingly
use the building block functions, sort and map, to create an
abstraction like the Schwartzian transform, then why do you
need to come up with special syntax or use a Sort::Module, as
it was suggested, to achieve just the same thing. my point
is that i wonder if it's useful for Perl or people who write
Perl, to bundle a map and sort function into some special
schwartzian syntax, is the goal just to abstract another layer
above the transform itself? why not just keep using map{} sort
map {}, if it's a well understand concept?
monty
James Mastros wrote:
On Thu, Mar 22, 2001 at 11:13:47PM -0500, John Porter wrote:
Brent Dax wrote:
Someone else showed a very ugly syntax with an anonymous
hash, and I was out to prove there was a prettier way to do it.
Do we want prettier? Or do we want more useful?
Perl is not exactly known for its pretty syntax.
If you have to explicitly specify both the forward and inverse transforms,
then it isn't very useful -- it's nothing more then map/sort/map. OTOH, if
you only have to specify the forward mapping, it becomes more useful. Thus,
I think the best syntax is
tsort({xform}, {compare}, @list), where the {}s are anon blocks or curried
expressions (same thing) and xform specifies the forward mapping (IE (lc
^_)) and compare specifies the comparator (IE (^_ cmp ^_)).
This would always (do the equiv to) create a LoL in the inner map, sort on
the -[0] elem, and extract the -[1] elem. Thus, it might not be as
effecent as a hand-crafted schwartzian, but will be at least as efficent as
a naieve straight sort (except in pathalogical cases, like tsort((^_),
(^_=^_), @list)).
-=- James Mastros
--
The most beautiful thing we can experience is the mysterious. It is the
source of all true art and science. He to whom this emotion is a stranger,
who can no longer pause to wonder and stand wrapt in awe, is as good as dead.
-=- Albert Einstein
AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
--
Mark Koopman
Software Engineer
WebSideStory, Inc
10182 Telesis Court
San Diego CA 92121
858.546.1182.##.318
858.546.0480.fax
perl -e '
eval(lc(join("",
map ({chr}(q(
49877273766940
80827378843973
32767986693280
69827639463932
39883673434341
))=~/../g;'
Re: Schwartzian Transform
Zenon Zabinski wrote: Personally, I have never used the Schwartzian Transform ... so I may not be fully knowledgeable of its usefulness. do you need to understand the intricacies if you can just cut and paste and just change a few variables? Not to be harsh, but you probably *do* need to understand the "intracacies" of the ST if you want to be able to contribute usefully to the resolution of this issue. -- John Porter
Re: Schwartzian Transform
"Brent" == Brent Dax [EMAIL PROTECTED] writes: Brent @s = schwartzian( Please, if we're going to add an operator, let's not call it schwartzian! I have enough trouble already telling people how to spell my name. :) Maybe I should have a kid named "Ian", so I can see on a roster some day: Schwartz,Ian :-) -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 [EMAIL PROTECTED] URL:http://www.stonehenge.com/merlyn/ Perl/Unix/security consulting, Technical writing, Comedy, etc. etc. See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
Re: Schwartzian Transform
Could someone summarize the arguments for such an operator? Doing so, to me, seems to subtrack from the scripting domain something which belongs there. Teaching the transform in classes is a wonderful way to both illustrate the power of Perl's map, and more importantly, help programmers understand the beauty of compact Perl. I'd hate to see that relegated to the "how-we-used-to-do-it" column in the name of making it easier. IMO the very quest for a name would be reason enough to not do it. "map_sort_map"? That begs the question. And since Randal asks that it not be named after him ... (I heard he filed a trademark on Schwartzian, so that's out. :) On 22 Mar 2001, Randal L. Schwartz wrote: "Brent" == Brent Dax [EMAIL PROTECTED] writes: Brent @s = schwartzian( Please, if we're going to add an operator, let's not call it schwartzian! I have enough trouble already telling people how to spell my name. :) Maybe I should have a kid named "Ian", so I can see on a roster some day: Schwartz,Ian :-) -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 [EMAIL PROTECTED] URL:http://www.stonehenge.com/merlyn/ Perl/Unix/security consulting, Technical writing, Comedy, etc. etc. See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
Re: Schwartzian Transform
"RLS" == Randal L Schwartz [EMAIL PROTECTED] writes:
RLS sort { $a/$b expression } { transforming expression, glued with $_ } @list
RLS so $a-[0] is guaranteed to be the original element, and the list-return
RLS value of the second block becomes $a-[1]... $a-[$#$a].
RLS So, to sort case insensitive (bad example :):
RLS @sorted = sort { $a-[1] cmp $b-[1] } { uc } @list;
RLS or to sort on GCOS and then username of password lines:
RLS @sorted = sort { $a-[5] cmp $b-[5] or $a-[1] cmp $b-[1] }
RLS { split /:/ } `cat /etc/passwd`;
RLS That captures the canonical ST pretty well, where $a-[0] is always
RLS the original element.
what everyone is missing in this thread, is that the real and sometime
tricky work is in key extraction and not the map/sort/map. there is no
easy way to describe how to extract multiple keys in the correct order
and then how to do the proper (ascending/descending, string/numeric)
comparisons on them. there are too many possibilities. i explored this
in depth as i designed the Sort::Records module. i had to invent a mini
language to describe all the possible key extractions and
comparisons. think along the lines of getopt::long but more powerful and
you can see the issues. try to describe how to extract this without
using perl code:
(split( ':', $rec-[2]{foo} ))[2]
and sort that numerically in descending order.
now add 2 more keys.
this would have to be a proper module and not a builtin op. there is no
reason to make this built in.
uri
--
Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com
SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting
The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books
The Best Search Engine on the Net -- http://www.northernlight.com
Re: Schwartzian Transform
this would have to be a proper module and not a builtin op. there is no reason to make this built in. This was essentially my point with regards to naming this op "map_sort_map". Just explaining the function of the op negates its usefulness *as* an op, because of the complexity of extracting the keys in order, and the subsequent comparisons. Imagine the perldoc entry.
RE: Schwartzian Transform
"Brent" == Brent Dax [EMAIL PROTECTED] writes:
Brent @s = schwartzian(
Please, if we're going to add an operator, let's not call it schwartzian!
I have enough trouble already telling people how to spell my name. :)
Which is why my real suggestion was a 'tsort' ('tsort' eq 'transform and
sort') operator. Someone else showed a very ugly syntax with an anonymous
hash, and I was out to prove there was a prettier way to do it.
BTW, I don't think 'schwartz' as the function name would be a good idea
either. Then I'd have to write something silly like
schwartz {$a = $b} {s/foo/bar/} @ary; #I see your Schwartz is as big as
mine... --Dark Helmet
Maybe I should have a kid named "Ian", so I can see on a roster some day:
Schwartz,Ian
:-)
:^)
--Brent Dax
[EMAIL PROTECTED]
This e-mail is a circumvention device as defined by the Digital Millennium
Copyright Act.
#qrpff
s''$/=\2048;while(){G=29;R=142;if((@a=unqT="C*",_)[20]48){D=89;_=unqb24,q
T,@
b=map{ord
qB8,unqb8,qT,_^$a[--D]}@INC;s/...$/1$/;Q=unqV,qb25,_;H=73;O=$b[4]9
|256|$b[3];Q=Q8^(P=(E=255)(Q12^Q4^Q/8^Q))17,O=O8^(E(F=(S=O147
^O)
^S*8^S6))9,_=(map{U=_%16orE^=R^=110(S=(unqT,"\xb\ntd\xbz\x14d")[_/16%8]
);E
^=(72,@z=(64,72,G^=12*(U-2?0:S17)),H^=_%64?12:0,@z)[_%8]}(16..271))[_]^((D
=8
)+=P+(~FE))for@a[128..$#a]}print+qT,@a}';s/[D-HO-U_]/\$$/g;s/q/pack+/g;eva
l
Re: Schwartzian Transform
Brent Dax wrote: Someone else showed a very ugly syntax with an anonymous hash, and I was out to prove there was a prettier way to do it. Do we want prettier? Or do we want more useful? Perl is not exactly known for its pretty syntax. -- John Porter
Re: Schwartzian Transform
Adam Turoff [EMAIL PROTECTED] writes:
We're all for making easy things easy, but the complexities of
"map {} sort {} map {} @list" has always been befuddling to newbies,
especially when reading the code left-to-right.
I've always thought that the purpose of the Schwartzian transform was
to separate newbies from Real Programmers.
:-)
-- Johan
Re: Schwartzian Transform
Uri Guttman wrote: records can be strings, or any perl [LH]o[LH]. y/L/A/; for a schwartz (drop the 'ian') or GR transform. Why? So it conforms with the "Guttman-Rosler" naming standard? -- John Porter
Re: Schwartzian Transform
On Wed, Mar 21, 2001 at 10:24:05AM -0500, John Porter wrote: Uri Guttman wrote: records can be strings, or any perl [LH]o[LH]. y/L/A/; for a schwartz (drop the 'ian') or GR transform. Why? So it conforms with the "Guttman-Rosler" naming standard? Which *I* would call "Macdonald transform" anyway :-) (John Macdonald suggested the trick to me at least a year before the GR paper, and it's there in the Sorting chapter, though it is not called by any special name...) -- John Porter -- $jhi++; # http://www.iki.fi/jhi/ # There is this special biologist word we use for 'stable'. # It is 'dead'. -- Jack Cohen
Re: Schwartzian Transform
"John" == John Porter [EMAIL PROTECTED] writes: John No special name, huh? Maybe that's the way it ought to be. That's the way I feel occasionally about the Schwartzian Transform, actually. Having to explain that it was named *for* me but not *by* me (in fact, actually to spite me, if I recall). Although it is fun when we get to the "Schwartizian Transform Illustrated" page in my slideset... I get to say "don't wait for the swimsuit issue... it's not a very pretty sight". -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 [EMAIL PROTECTED] URL:http://www.stonehenge.com/merlyn/ Perl/Unix/security consulting, Technical writing, Comedy, etc. etc. See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
Re: Schwartzian Transform
"JP" == John Porter [EMAIL PROTECTED] writes: JP Uri Guttman wrote: records can be strings, or any perl [LH]o[LH]. JP y/L/A/; tell that to perllol :) for a schwartz (drop the 'ian') or GR transform. JP Why? So it conforms with the "Guttman-Rosler" naming standard? that has been discussed elsewhere. the 'ian' suffix is overkill. think about all the classic mathematical transforms and they don't append 'ian' to the person's name. fourier, laplace, etc. maybe schwartzian sounds better but it is odd (and probably grammatically wrong) to add 'ian' to his name for this use. but i doubt it will be dropped as it is reached a critical mass of acceptance. uri -- Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books The Best Search Engine on the Net -- http://www.northernlight.com
Re: Schwartzian Transform
Uri Guttman wrote: JP y/L/A/; tell that to perllol :) I do, through clenched teeth, every time I see it. "Perl: Laughing Out Loud" :-) the 'ian' suffix is overkill. think about all the classic mathematical transforms and they don't append 'ian' to the person's name. fourier, laplace, etc. I find tons of counter-examples. Lorentzian. Newtonian. Langrangian. Smithsonian. Brownian. Wronskian. Boolean. Gaussian. Keplerian. Orwellian. Hegelian. Russellian. Gregorian. Dickensian. Cartesian. Bayesian. Edwardian. Lucasian. Pavlovian. Euclidean. Laplacian. Darwinian. Hamiltonian. Jeffersonian. etc. I don't think adding "-ian" to a name to make it an adjective is particularly bizarre. It also doesn't seem to violate any rules of grammer that I know of. And there's nothing special about a transform, that different rules would apply to it anyway. maybe schwartzian sounds better Indeed; afaict, how a proper noun is converted into an adjective seems to depend *entirely* on how it sounds. There's no reason it couldn't be "Hawkingian radiation" except that absolutely no one would say that! -- John Porter Useless use of time in void context.
Re: Schwartzian Transform
On Wed, 21 Mar 2001 15:40:20 -0500, John Porter wrote: Uri Guttman wrote: JP y/L/A/; tell that to perllol :) I do, through clenched teeth, every time I see it. IMHO, it is: HoA HoH LoA LoH -- Bart.
Re: Schwartzian Transform
Bart Lateur wrote:
IMHO, it is: HoA, HoH, LoA, LoH
But that's only two levels, when the number of levels
can really be unbounded. Only the *top* level can be
a list, rather than an array.
Since any two levels can have a relationship
...-[0]-[0]-...
...-[0]-{X}-...
...-{X}-[0]-...
...-{X}-{X}-...
that calls for AoA, AoH, HoA, HoH.
--
John Porter
Useless use of time in void context.
Re: Schwartzian Transform
Loooking over dev.perl.org/rfc, only two RFCs mention sorting: RFC 124: Sort order for any hash RFC 304: sort algorithm to be selectable at compile time and none mentioning the Schwartz. :-) This message is not an RFC, nor is it an intent to add a feature to Perl or specify a syntax for that feature[*]. I just posted it to get the idea into the archives as a (possibly) useful way to improve Perl. Well, why the disclaimer? If it is a 'useful way to improve Perl', then it *is* an intent to add a feature. And in a looser sense of the word, it is a Request For Comments. You are asking for comments on a whether or not a given feature would be good to have natively in perl, right? And I've seen too many 'good ideas' get lost in the noise by just stating them as emails, so I wouldn't trust archiving via email list. So, I'll ask it again - why are RFCs so horrid? And why the artificial deadline for them? Ed
Re: Schwartzian Transform
Hey, I just have a couple of ideas that may either make me look like a fool or provoke some discussion: Personally, I have never used the Schwartzian Transform (but I have heard, looked at it), so I may not be fully knowledgeable of its usefulness. However, do the advantages of including it outweigh the disadvantages? I have read all of the messages on this topic to this point and I haven't seen much discussion from this aspect, but a lot on what the function would be named, etc. The argument for including this was that many newbies may not be able to understand it very well. But, do you need to understand the intricacies if you can just cut and paste and just change a few variables? Couldn't it be included as a module and be implemented basically the same way? Over my long experience with perl (not even one year :-) ), I have heard a lot about it being slow. Wouldn't adding functions like this just make it needlessly slower? Please correct me if I am wrong. I am just trying to begin some discussion from this point of view. -- Zenon "zdog" Zabinski
Re: Schwartzian Transform
John Porter declared:
Adam Turoff wrote:
This message is not an RFC, nor is it an intent to add a feature to Perl
or specify a syntax for that feature[*].
Yay.
We're all for making easy things easy, but the complexities of
"map {} sort {} map {} @list" has always been befuddling to newbies,
especially when reading the code left-to-right.
So you think
@s =
map { $_-[0] }
sort { $a-[1] = $b-[1] }
map { [ $_, /num:(\d+)/ ] }
@t;
would be more clearly written as
@s = schwartzian(
{
second_map = sub { $_-[0] },
the_sort= sub { $a-[1] = $b-[1] }, first_map = sub { [
$_, /num:(\d+)/ ] },
},
@t );
---
How about this?
@array=tsort
{ /num:(\d+)/ }
numerically #optional
@array;
is handled by something like
tsort(;@) {
my $t=shift;
my $s=shift || sub { $a cmp $b };
my @a=@_ || (something);
return
map { $_-[0] }
sort {
$a=$a-[1];
$b=$b-[1];
$s;
}
map { [ $_ , $t ] }
@a;
}
It's totally untested, but you get the idea...
Or, a slightly different syntax from yours:
schwartzian {
first {...}
sort {...}
last {...}
} @ary;
--Brent Dax
Excuse typos, it's hahd to write on a Palm...
Re: Schwartzian Transform
Adam Turoff wrote:
This message is not an RFC, nor is it an intent to add a feature
to Perl or specify a syntax for that feature[*].
Yay.
We're all for making easy things easy, but the complexities of
"map {} sort {} map {} @list" has always been befuddling to newbies,
especially when reading the code left-to-right.
So you think
@s =
map { $_-[0] }
sort { $a-[1] = $b-[1] }
map { [ $_, /num:(\d+)/ ] }
@t;
would be more clearly written as
@s = schwartzian(
{
second_map = sub { $_-[0] },
the_sort= sub { $a-[1] = $b-[1] },
first_map = sub { [ $_, /num:(\d+)/ ] },
},
@t );
???
I guess that would allow reordering the functions:
@s = schwartzian(
{
first_map = sub { [ $_, /num:(\d+)/ ] },
the_sort= sub { $a-[1] = $b-[1] },
second_map = sub { $_-[0] },
},
@t );
Is that really an improvement?
Every programmer understands right-to-left data flow when it's
written with parentheses. Perl novices just need to understand
that
map { } sort { } map { } @
is a mere syntactic rewrite of
map( , sort( , map( , @ ) ) )
--
John Porter
Useless use of time in void context.
Re: Schwartzian Transform
"JP" == John Porter [EMAIL PROTECTED] writes:
JP Is that really an improvement?
JP Every programmer understands right-to-left data flow when it's
JP written with parentheses. Perl novices just need to understand
JP that
JP map { } sort { } map { } @
JP is a mere syntactic rewrite of
JP map( , sort( , map( , @ ) ) )
well, if anyone is so inclined, they can take over my Sort::Records
module which is gathering major dust. it could be a standard module in
perl6 and help out lots of people. its goal was/is to have the code
describe the sort fields in any complex data tree or string. the module
generates the perl code to extract the fields into a GRT makes a sub out
of that. then you can pass that object lists of records and then do a
sort. you can print out the generated code too for cutting and
pasting. the sort object is reusable with other lists of data. input
records can be strings, or any perl [LH]o[LH]. actual sort keys have to
be scalars and they can be extracted via m// or substr or even custom
callback code.
so this eliminates the need to explicitly use map/sort/map and does all
the key extraction and record management. no need to figure out the code
for a schwartz (drop the 'ian') or GR transform.
the basic design and coding was done but not finished. it got code
reviewed and than i shelved it.
any interest? i would help out but i can't drive the project now.
uri
--
Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com
SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting
The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books
The Best Search Engine on the Net -- http://www.northernlight.com
Re: Schwartzian Transform
On Tue, Mar 20, 2001 at 11:15:51PM -0500, John Porter wrote:
@s = schwartzian(
{
second_map = sub { $_-[0] },
the_sort= sub { $a-[1] = $b-[1] },
first_map = sub { [ $_, /num:(\d+)/ ] },
},
@t );
Hm. I'd rather see:
schwartzian({/num:(\d+)/}, {^_=^_}, @t), and have perl figure out how to
do the forward and backword mappings. Hmm, I don't see why you couldn't
write that right now. (Other then synthatical shugar -- currying and
getting rid of the need for "sub {}"s.)
Indeed,
map $_-[0], sort {$sort($a-[1], $b-[1])} map [$_, $attrib($_)], @list;
does what I intendeded. (Where ex $sort = sub {$_[0] cmp $_[1]}, and
$attrib = sub {lc $_}.) (Of course, this doesn't always use the optimal
form.)
-=- James Mastros
--
The most beautiful thing we can experience is the mysterious. It is the
source of all true art and science. He to whom this emotion is a stranger,
who can no longer pause to wonder and stand wrapt in awe, is as good as dead.
-=- Albert Einstein
AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
