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
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
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);
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
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
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
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
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
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
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
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
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
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
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
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
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
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] },
"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
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
"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
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?
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
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) }
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
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
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?
--
"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
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
"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
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.
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
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
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
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
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.
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
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
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
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
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
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
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
Tad McClellan wrote:
Nothing like throwing some disk accesses into it if slow is what
you seek.
Yeah. Or web fetches!
--
John Porter
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
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
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
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?
"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],
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
"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
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
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
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
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
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
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
"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:
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
"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
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
"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
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
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
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
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
"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 spit
"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
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,
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.
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}-...
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
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
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,
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
"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
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+)/}, {^_=^_},
76 matches
Mail list logo