Random Permutations

[Janis Voigtlaender]

Andreas Abel wrote:
> Well, sorting is a special case of permuting, so my idea was to use the library
> routine
> 
>    List.sortBy :: (a -> a -> Ordering) -> [a] -> [a]
> 
> passing it a comparison function which ignores its arguments and simply returns
> a random bit when invoked, e.g.
> 
>    permute = sortBy $ \_ _ -> if random() then GT else LT
> 
> Unfortunately, this one-line hack is impossible since random numbers rely on
> state and sortBy is not prepared for use with a monad.

Well, even if it were possible to use sortBy with a monad, wouldn't your
hack be a bit dangerous? Here is what the report has to say on sortBy:

"... when the "By" function replaces an Ord context by a binary
predicate, the predicate is assumed to define a total ordering."

Clearly, (\_ _ -> if random() then GT else LT) does not make for a total
ordering. While you might say that this is no problem, since you don't
actually want to *sort*, you might even get nontermination, if the
implementation of sortBy happened to use the property "total ordering"
for ensuring termination (as, e.g., a naive implementation of bubblesort
does).

Regards, Janis.


--
Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt@tcs.inf.tu-dresden.de