The link in that node is no longer valid, but it can be found on Uri's site http://www.sysarch.com/ here: http://www.sysarch.com/Perl/sort_paper.html.
The paper is quite old, but sorting hasn't changed much in 5 years! The main reason I am posting it here in Meditations is that this is the first document I have read that made me realise in only a few minutes exactly what the Schwartzian Transform does! It is basically a standard pre-caching sort manouvre, but using a pipeline of anonymous arrays instead of a temporary named hash.
Other than that, the paper is a good refresher of all that sorting algorithm thinking that you can never quite remember from University...
Update: Corrected the spelling of Uri's name - thanks sauoq
It's quite strange for me to see someone refer to such a recent work as "quite old". Newton's Principia is quite old; The Guttman-Rosler paper is quite new. :-)
The Egyptian Book of the Dead is quite old; Newton's Principia is quite new. :-)
I wish there was a better name for it, something along the lines of keying records for the purpose of sorting.. it certainly is not some amazing special technique that could be one-day patented!
Erm, no, Python's "decorate-sort-undecorate" is closer to the GRT than the Scwhartzian Transform ... as pointed out in this "old" fwp thread. Curiously, and following on from this, some years later davorg received a surprise free copy of the 2nd edition of the Python Cookbook! :-)
See also this classic "old" PM node: node 145659.
Last I checked, Perl6 was also supposed to support decoupling the key comparison from the extraction of keys from list elements. In Perl5, key extraction is conflated with comparison in a single sub, which means the key extraction code for $a is often copypasted for $b. Given that key extraction is decoupled from comparison, you’d also often need simple forms of comparison only, so there were ideas being bandied about for a more declarative comparison syntax for those forms.
Now the motivation for all this was to reduce duplication and make the trivial cases simpler, but such syntax would neatly allow the runtime to do ST sorting internally, without the programmer having to do anything explicit about it.
I don’t know what came of it, but I’d be surprised if it hasn’t made it into the current form of Perl6 in some shape. I should go look into this.
Makeshifts last the longest.
On a related note, I know that you can chain the word "and" 5 times in a row in a gramatically correct English sentance - what's the most number of "is"s that people can chain together? I can do 3.
Yes I know it's not really related, but I can never write a sentance with "is is" without then wondering :)
Update:The contents of this post are a work of fiction, for amusement purposes only.
Any correspondence between concepts and constructs it contains and any real literary entities of similar name or form are purely coincidental, as the author hasn't got a clue!
That that is one of the words that can be grammatically correctly abutted within a sentence is no surprise, as just demonstrated.
And and can also be so abutted.
In these usages of that that, and and and, the first repetition is referring directly to the second.
But that that that and and and, are not the end to these linguistic anomalies.
He said the matter was closed, and that that should be an end to it.
In this usage, the first that is not referring to the second that.
Once the sentence itself starts both using this phenomena and referring to it, the 'that that', that that 'that that' is referring to can itself become self-referential, with the consequence that that, that that, that that, that that refers to, tends to become obscured.
However, is it a matter of speculation whether is, is another word that can be so abutted?
Apparently not :)
Is is is?
"Is is is?" is "Is is is?"
"'Is is is?' is 'Is is is?'" is 'Is is is?' is 'Is is is?'"
"'"Is is is?" is "Is is is?"' is '"Is is is?" is "Is is is?"' is '"Is is is?" is "Is is is?"' is '"Is is is?" is "Is is is?"'"
etc.
(Note that parsing grammatically correct English sentences is an NP hard problem.)
(Note that parsing grammatically correct English sentences is an NP hard problem.)I feel like I've seen this claim mentioned before here on PM, although I can't find anything via super search. It's not something that I've heard about anywhere else. Do you have a source for this? A natural reduction from, say, 3-SAT to English grammaticity would be quite interesting indeed. I wonder if the subset of English grammar that is used consists of fairly standard constructions, and not obscure things that native speakers may disagree on.
blokhead
He said the matter was closed, and that that should be an end to it.
The word 'that' is one of the only words I can think of that I dislike. There are so many instances where I'm not sure whether including the word is necessary or even gramatically correct. I tend to understand the concept behind doubling the word 'that', as in my quoted example. The second occurance of the word in this case is referring back to the previous sentence (or rather, the object or idea to which the speaker is referring to as being the last item being spoken about the matter).
I am trying to think up a simple sentence where the word 'that' can be used, but seems to make the exact same sense if you pull the word out. I come across these a lot when writing, but can't seem to invent one now. I bet this issue is dealt with in university English classes at some point :)
I am trying to think up a simple sentence where the word 'that' can be used, but seems to make the exact same sense if you pull the word out.
One example comes to mind
$self->nod();
I take it both are equally correct?
Yes. Both are in common usage, at least in spoken English hereabouts, but the second form (I think) would be the preferred form as 'that' is redundant. It sounds better, to my ears at least.
Would the sentence, "I put dashes between Fish and And and And and Chips in my Fish And Chips sign" be clearer if I put commas between Fish and and, and and and And, and And and and, and and and Chips?
As for is, it is kind of cheating, but, "Is is is?" is "Is is is?"
However the real record holder is buffalo. Buffalo can mean the city, the animal, or "to bewilder and confuse". Between those three meanings you can always find a correct gramatical parse for the word Buffalo, repeated any number of times. For instance, Buffalo buffalo buffalo buffalo buffalo Buffalo buffalo! means "Buffalo buffalo bewilder and confuse buffalo that bewilder and confuse Buffalo buffalo."
Didn't Clinton base his whole defense on that? :-)
I'm not really a human, but I play one on earth. flash japh
Another one I like from there is "Bulldogs bulldogs bulldogs fight fight fight!" The yale cheer (and also a grammatical sentence). Theoretically this can be embedded as many times as you want and still be grammatical, but the human grammar processor is typically incapable of more than three levels of embedding.
James, while John had had "had" had had "had had". "Had had" had had a better effect on the teacher.
That's seven hads in a sentence, with eleven across a sentence break.
Michael
Then, there was the proposal that a second John and Jim had been given this sentence to punctuate, and the second John had given up in disgust:
John, where Jim had had, "John, where Jim had had 'had', had had 'had had'", had had "John where Jim had had had had had had had".It's probably time to let sleeping hads lie at this point.
Evan Carroll
www.EvanCarroll.com