[Haskell-cafe] generalized shuffle

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


I have implemented a generalized shuffle function, for the 
random-shuffle package

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:

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