[racket] on reversing a list by way of sort

On Mon, Sep 15, 2014 at 8:50 PM, Asumu Takikawa <asumu at ccs.neu.edu> 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)

This is different than linked algorithm. This one assigns a random
number from [0,1) to each element where the linked algorithm assigns a
random pairwise ordering to each comparison.

I don't think there is anything wrong from a correctness standpoint on
the stdlib's algorithm.

>
> Cheers,
> Asumu
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users