[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: comic-book-insult

From: Emanuel Berg
Subject: Re: comic-book-insult
Date: Mon, 09 Sep 2019 19:41:10 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)

Yuri Khan wrote:

>> (rand-chars (sort chars (lambda (_ __) (zerop (random 2)))))
> If you were to pull off this kind of thing in
> C or C++, that would be classified as
> undefined behavior and possibly cause demons
> to fly out your nose. The comparison
> predicate used in sorting algorithms must be
> a strict weak ordering, i.e.
> * irreflexive — (not (p x x)) for each x;
> * antisymmetric — if (p x y), then (not (p y x));
> * transitive — if (p x y) and (p y z), then
>   (p x z);
> * the equivalence induced by it must also
>   be transitive — if (not (or (p x y) (p y x)))
>   and (not (or (p y z) (p z y))), then (not (or
>   (p x z) (p z x))).
> A predicate that returns a random boolean on
> each invocation will easily violate any or all
> of the above. [...]

Interesting, however does Computer Science
theory of sorting apply even when the intention
is to randomize the elements?

> The canonical lazy coder way to random-shuffle
> a collection is to first associate a random
> value with each element, then sort by that:
> (concat (seq-map #'car (seq-sort-by #'cdr #'<
> (seq-map (lambda (x) (cons x (random)))
> (string-to-vector "@#$%&")))))

The coder can't be that lazy:

    seq-map: Symbol’s function definition is
    void: seq-sort-by
underground experts united

reply via email to

[Prev in Thread] Current Thread [Next in Thread]