# [Haskell-cafe] generalized shuffle

Manlio Perillo manlio_perillo at libero.it
Mon Mar 23 19:35:53 EDT 2009

```Hi.

I have implemented a generalized shuffle function, for the
random-shuffle package
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/random-shuffle

I have not yet commited the change, before that I would like to receive
some feedbacks (especially by the original author of the shuffle
function, in Cc)

The new function is defined in this example:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2808

Note that it make use of functions not exported by the
System.Random.Shuffle module.

I have generalized the original shuffle function in two ways:

1) It is now possible to obtain a random "sample" from a sequence,
by doing, as an example:
shuffles [1..10] [2, 3, 4, 2, 1]

Note that this is equivalent at taking the first 5 elements of the
full shuffled sequence, and the performance are pratically the same.

2) It is now possible to pass an infinite "r-sequence" to the shuffle
function, as an example:
shuffles [1..10] \$ cycle [9, 8 .. 1]

The result is an infinite list, with elements cyclically extracted
from the "r-sequence".

When the "r-sequence" contains random numbers, we get an infinite
sequence containing all possible random "choices" of elements in the
original sequence.

Why I'm doing this?
The reason is that in a project I need to extract random elements
from a list (and I need to extract a lot of them), and using "normal"
methods [1] seems to be rather inefficient.

Using the `shuffles` function should be much more efficient, since it
uses a tree, and this tree is built only once.

[1] by normal method I mean: extract a random number, in the range
[0, n] (where n is the length of the sequence), and get the element
indexed by that number.

Indexing for a list if very expensive.
And it is not very fast, even using arrays (unless you use
non portable unsafeRead).

Thanks  Manlio Perillo
```

More information about the Haskell-Cafe mailing list