Talk:Schwartzian transform

Who the heck thought this wikicode was easier to read than the original Perl?

@new = map { $_->[0] }
       sort { $a->[1] <=> $b->[1] }
       map { [$_, foo($_)] }
       @old;

At least include the Perl for comparison. I've seldom seen a Schwartzian Transform outside of Perl. grendel|khan 17:43, 2005 Mar 7 (UTC)

The wikicode is easier to read for people who are not accustomed to the functional programming style and perl punctuation. Luckily, both versions are in the article now. --TuukkaH 08:33:40, 2005-09-09 (UTC)

---

I prefer the Python version:

new = [p[1] for p in sorted([(criterion(e), e) for e in old])]

- Fredrik | talk 15:59, 24 Mar 2005 (UTC)

This needs Python version 2.4 because sorted is used. But on Python 2.4 the programmer doesn't need to write the transformation, because sort and sorted accept the keyword argument key=criterion. Now a guestion remains whether Python internally uses the transformation or a less efficient sort. It seems it uses the transformation: "-- cmp is called multiple times for each list element while key and reverse touch each element only once." (2.3.6.4 Mutable Sequence Types) --TuukkaH 08:33:40, 2005-09-09 (UTC)

---

Alterego, can you explain why you reverted my changes? The old version of the Python 2.3 code didn't actually run, and the old version of the 2.4 code was a needlessly long way round. Matthew Woodcraft 17:40, 28 July 2005 (UTC)

Perhaps we should explain the Python alternatives to the reader better. --TuukkaH 08:33:40, 2005-09-09 (UTC)

---

Maybe it should be noted that its not the comparsion that is heavy, but the evalution of the operand expressions? --MattiasW

Rewrite

Per comments below, I am going to rewrite this article so that it features a simple example of the idiom in Perl, a pseudocode implementation, concise history, and context in other programming languages. The wikibook algorithm page is messed up and also needs to be rewritten. I don't know anything about Python - however, I think what's notable about "Schwartzian Transformation" and Python is not the illustration of a Python implementation, but the fact that the Python community adopted the Perl term to describe an idiom that looks and behaves different in Python.

The Schwartzian Transform in Perl is a fairly difficult construct to understand, and I don't have any problem with presenting an explanation that, while accurate, requires some study to comprehend.

Finally, while I understand the desire to move material that should better be in a programming book into the algorithm wikibook, this is an article about a programming idiom, and there is no need to ask a reader to go seek essential information elsewhere. Joseph N Hall 23:38, 30 August 2006 (UTC)

I cleaned up the page, clarifying the difference between the "Schwartzian transform" idiom and other versions of the underlying algorithm, displaying the actual idiom more prominently and explaining it, while also keeping a procedural example of a similar algorithm. This also addresses some contradictions present in the previous version (stemming from the confusion between the idiom and the algorithm). 87.17.241.194 19:17, 20 September 2006 (UTC)

Perl

It's just plain stupid that the page for the term Schwartzian Transform, which is immutably bound to the phrase coined to describe Randal's original (in)famous USENET post way back in 1995(?), doesn't feature an example in Perl. For God's sake, people.

Also, the article is, as I write, friggin' incoherent. Joseph N Hall 09:39, 26 August 2006 (UTC)

If the article is incoherent, it should be improved with text or pseudocode. The purpose of the Wikipedia article is to present the concept and its history, and it should be capable of explaining it to people unfamiliar with Perl or Ruby. As far as I understand, the concept of a Schwartzian transform can be implemented in any language; the fact that Schwartz popularized it in Perl needs to be mentioned, but it doesn't make the Perl version special. ~ Booya ^Bazooka 18:35, 26 August 2006 (UTC)

You're missing my point completely, and apparently the points made by every other contributor to this article. The article isn't about "functional programming." It's about "The Perl thing that Randal Schwartz started posting on USENET shortly after the release of Perl 5," which was then popularized in the Perl community under that name. It's all well to illustrate the general concept in pseudocode by way of comparison, but to remove the Perl context and the source code from the article is severely misleading revisionism. I am still shocked by the current form of this article. Joseph N Hall 23:44, 26 August 2006 (UTC)

Also, perhaps the article should be split, to separate the history of the term "Schwartzian Transform" from the underlying algorithm. They are really two different things. At the least there should be a "History of the term" secion. But what we have now is a jumble that's impossible to read and/or follow, especially with the redirect to the implementation article (which is also in serious need of editing and rewriting). As soon as a couple of other people chime in (hopefully User:RandalSchwartz and User:Dominus), I will probably rewrite this article. I know, it was all probably done with good intentions, but the result is currently poor. Joseph N Hall 23:59, 26 August 2006 (UTC)

I'm not sure what point "every other contributor to this article" was trying to make. The entire article summary, none of which was edited by me, describes 'Schwartzian transform' as a programming technique which existed before Schwartz popularized it in Perl.

I would rather you go ahead and start rewriting things, rather than just complain about how bad it is. The only point I am arguing is that the Wikipedia article should not be full of Perl code. And the only edit I have ever made to this article has been to separate the Perl from the English, a decision by which I still stand. ~ Booya ^Bazooka 08:21, 27 August 2006 (UTC)

I agree that it's a bit silly to not have a Perl example as the first example there, perhaps as part of a history description. I also agree that while the technique has been around for ages, this page should be describing the specific term, which is a Perl-world term, although perhaps adopted by others as time has gone on. --Randal L. Schwartz 18:52, 27 August 2006 (UTC)

I transwikied all of the language-specific code, in this and a number of other articles, because these programming-related articles were becoming little but code repositories. Perhaps it was inappropriate in this article; I'm not going to press my opinion too hard in this article, since I'm unfamiliar with the subject. But please keep in mind that inclusion of code implementations borders on original research, and even though this is largely a "Perl term", it is in everyone's best interest to keep the article as accessible as possible. ~ Booya ^Bazooka 19:28, 27 August 2006 (UTC)

But please keep in mind that inclusion of code implementations borders on original research -- No, whether something is written in English or Perl (or MathML or runes) has nothing to do with whether it is original research. Writing source code in order to illustrate an idiom is not original research; nor is quoting code in order to illustrate a historical event. Joseph N Hall 00:14, 29 August 2006 (UTC)

History Lesson

For reference, the earliest appearance of the transform in Perl in print (USENET, that is) is apparently this thread in comp.unix.shell. Randal was a LISP programmer and expressed this functional programming construct in Perl 5. The popularization of the term "Schwartzian Transform" (and perhaps the coinage itself) is probably due to Tom Christiansen, although various combinations of "Schwartz" and "transform" may have appeared before Christiansen gave the construct its enduring name. Bennett Todd referred to it as the "Schwartz transformation" in this article in August 1995. It is covered formally in both Christiansen's 1995-vintage perllol man page ("lists of lists") and Randal's January 1996 UnixReview column. Joseph N Hall 10:22, 26 August 2006 (UTC)

Notice that the Schwartzian Transform requires Perl 5, which was released on October 17, 1994, only 2 months before Randal's above-referenced post to comp.unix.shell. Joseph N Hall 10:31, 26 August 2006 (UTC)

I know little about Python, but apparently the term "Schwartzian Transform" had made its way into the Python community as early as 2001, if the date on this posting is accurate. Joseph N Hall 00:04, 29 August 2006 (UTC)

As of today, the article says:

(The current version of the Perl Timeline is incorrect and refers to a later date in 1995.)

I believe this is based on Randal's own recollection over at [1]. According to Randal, it was in that April thread that Tom Christiansen stepped in with the naming bit, which is likely why the Dec 1994 thread didn't make it into the Perl Timeline. So, I guess the is incorrect verbiage is a bit blunt here. BACbKA (talk) 05:23, 24 May 2013 (UTC)

I would also like to make it clear somehow that I did not name it after myself. It was Tom Christiansen who named it after me on his much longer followup post. This phrase is a bit misleading: "However, the algorithm was already in use in other languages (under no specific name) before it was popularized among the Perl community in the form of that particular idiom by Schwartz.". It is indeed quite possible that I used the terminology later, after everyone else started calling it that. Randal L. Schwartz (talk) 17:15, 31 May 2021 (UTC)

modify the Schwartz idea for more speed

The access to index 0 is often more quick than to other indexes but never slower. sort has more index accesses than the first written map.

@new = map  { $_->[1] }
       sort { $a->[0] <=> $b->[0] }
       map  { [foo($_), $_] }
       @old;

Steffen Winkler, http:://erlangen.pm.org/ 88.65.95.170 (talk) 05:43, 31 May 2008 (UTC)

Curious. Where do you get the idea that accessing index 0 is faster than index 1? --Randal L. Schwartz (talk) 07:56, 31 May 2008 (UTC)

It's a tiny bit faster, because you don't have to do the multiplication by element size and the addition to the array origin to get the address of the element, but this is a lot of work for a compiler to do for such a small gain, at least it seems to be. I don't know if anyone has instrumented it, or if the Perl compiler already does this optimization. If not, maybe we need a special Schwartzian transform operation in an optimized module written directly in C that would take advantage of this.Bostoner (talk) 21:24, 17 November 2009 (UTC)

BTW, I don't know if there is a name for this, but if the operation is reversible, depending on how expensive it is, it might in some cases be faster to transform each element and then transform them back. I do this to sort pathnames by directory (so all of the files in the same directory are next to each other then in alphabetical order). I replace each path separator with a null character, sort, and replace the nulls with the separator again.Bostoner (talk) 21:24, 17 November 2009 (UTC)

I originally wrote the ST a lot like this, but then I switched to always having the 0 element be the original value, for consistency. Some uses of the ST involve multiple keys, for example, so they'd end up as elements 1, 2, 3, etc. --Randal L. Schwartz (talk) 01:31, 18 November 2009 (UTC)

Perl 6 example

I have removed the Perl 6 example, as it did not do the same thing at all, rather performed a case-insensitive sort:

Later, Perl 6 has improved on the code length considerably:

 # (Perl 6)
 
 @a = @a.sort: { .uc };

TimR (talk) 14:36, 13 May 2009 (UTC)

References

is a Programming idiom

Does anyone have WP:V sources that can confirm this? Ushkin N (talk) 17:26, 30 May 2016 (UTC)

To my great surprise I have been unable to find a reliable source that would explicitly refer to the Schwartzian transform as a programming idiom. So, what do we call it? (As of now, the lede continues to call it an idiom.) – Tea2min (talk) 06:13, 31 May 2016 (UTC)

Well that was my point exactly. None of them use "Programming idiom", I suggest to use Category:Programming language topics because it is almost always true. Ushkin N (talk) 11:37, 31 May 2016 (UTC)

• Python Cookbook: "The DSU idiom builds an auxiliary list, whose items are tuples where each item of the original list is preceded by a “key”. ... DSU is also sometimes known, not quite correctly, as the Schwartzian Transform"
• Learning Python: "As a more interesting example, let's see the decorate-sort-undecorate idiom (also known as Schwartzian transform)."

—Ruud 08:50, 31 May 2016 (UTC)

Thanks. It didn't occur to me to look in a Python book. So that's Martelli, Alex; Ascher, David, eds. (2002). "2.3 Sorting While Guaranteeing Sort Stability". Python Cookbook. O'Reilly & Associates. p. 43. ISBN 0-596-00167-3. This idiom is also known as the "Schwartzian transform", by analogy with a related Perl idiom. – Tea2min (talk) 09:00, 31 May 2016 (UTC)