[racket] on reversing a list by way of sort

Haha, yes I too checked Racket `shuffle` after I read that. But 
`shuffle` is mathematically sound. (Was I really surprised?) It doesn't 
use a random comparator. Rather, it assigns random *keys* to the 
elements and then uses a standard `<` comparator, which preserves 
transitivity (net of the nanoscopic chance of `random` returning the 
same key twice).

I also verified this experimentally using Bostock's bias-correlation 
technique. Here's Racket `shuffle` on a 10-card deck, shuffled a million 
times (truly random shuffling will produce values close to zero):

+0.0037     -0.0037     +0.0107     -0.0087     +0.0049     +0.0432     
-0.0306     +0.0025     -0.0319     +0.0099
-0.0589     +0.0066     +0.0295     -0.0337     -0.0308     +0.0288     
-0.0106     +0.0375     +0.0202     +0.0114
-0.0191     +0.0381     -0.0308     -0.017     +0.0608     -0.0609     
+0.0183     +0.0037     -0.0037     +0.0106
-0.0025     -0.0232     -0.0135     -0.0166     -0.0127     -0.0104     
+0.0444     -0.0087     +0.0275     +0.0157
+0.0537     -0.0114     -0.0138     +0.0029     +0.0281     -0.0264     
-0.0369     +0.0237     -0.0051     -0.0148
+0.0075     +0.0254     -0.0128     +0.048     +0.0309     -0.0053     
-0.0055     -0.046     -0.0183     -0.0239
+0.0211     +0.005     -0.0162     +0.0326     -0.0019     -0.0062     
-0.0423     -0.0036     +0.0501     -0.0386
+0.027     +0.0228     -0.0327     -0.001     -0.0256     +0.013 +0.0005 
     +0.0203     -0.0157     -0.0086
-0.0039     -0.059     +0.0769     -0.0294     -0.0045     +0.0046     
+0.0121     -0.0035     -0.0344     +0.0411
-0.0286     -0.0006     +0.0027     +0.0229     -0.0492     +0.0196     
+0.0506     -0.0259     +0.0113     -0.0028

And here's the evil random-comparator shuffle, which you write thus: 
(sort l (λ(a b) (< (random) 0.5)) #:cache-keys? #t)

+5.5262     +5.3953     +0.2165     -4.1699     -6.8645     +5.3694     
+5.3138     +0.2238     -4.1352     -6.8754
+5.3552     +5.5478     +0.2443     -4.1483     -6.8783     +5.2901     
+5.3356     +0.3061     -4.1741     -6.8784
+4.0834     +4.0231     +1.1727     -3.128     -6.0845     +4.0658     
+4.0908     +0.9624     -3.0706     -6.1151
+2.2696     +2.3085     +1.3081     -1.1473     -4.5383     +2.236     
+2.1868     +1.2539     -1.3606     -4.5167
+0.2824     +0.2988     +1.0478     +0.3734     -1.7924     +0.264     
+0.2866     +0.9759     +0.2977     -2.0342
-1.1146     -1.1627     +0.4308     +1.2617     +0.452     -0.885     
-1.1186     +0.4888     +1.2433     +0.4043
-1.6973     -1.7075     -0.0871     +1.4717     +1.8591     -1.6837     
-1.4007     -0.087     +1.4763     +1.8562
-2.9075     -2.945     +0.3826     +2.2916     +3.0588     -2.9184     
-2.9246     +0.5772     +2.3114     +3.0739
-4.9106     -4.8946     -0.9329     +4.7021     +5.8784     -4.8757     
-4.8899     -0.942     +4.9596     +5.9056
-6.8868     -6.8637     -3.7828     +2.493     +14.9097     -6.8625     
-6.8798     -3.7591     +2.4522     +15.1798

QED


On 09/15/14 8:50 PM, Asumu Takikawa wrote:
> On 2014-09-15 18:57:51 -0700, Matthew Butterick wrote:
>> Mike Bostock's visual demonstration of why naive sorting functions are false
>> friends. As he and Henglein point out, transitivity of the comparator is
>> essential.
>>
>> http://bost.ocks.org/mike/shuffle/compare.html
> Thanks, that's really interesting. Also means that our implementation of
> `shuffle` in Racket stdlib is not great:
>
>    (define (shuffle l)
>      (sort l < #:key (λ(_) (random)) #:cache-keys? #t))
>
> (more prose on the algorithm here: http://bost.ocks.org/mike/algorithms/#shuffling)
>
> Cheers,
> Asumu