Add a shuffled list generator

[NathanReb]

This PR adds a shuffle: 'a list -> 'a list gen generator using Fisher-Yates algorithm.

I tested it with a toy program and it seems to work pretty well!

Let me know what you think!

[stedolan]

Thanks! (I broke this by removing Const, so I pushed a fix to your branch before merging)

[pqwy]

Two points:

• Shuffling arrays is easier than shuffling lists (Oleg described a list version of F-Y at some point). Maybe shuffle should generate arrays, and let the user convert to/from their desired sequence type?

• It might be worthwhile to get rid of dynamic_bind. Something like:

let rec sequence = function
  g::gs -> map [g; sequence gs] (fun x xs -> x::xs)
| [] -> const []

let shuffle arr =
  let n = Array.length arr in
  let xs = List.init n (fun i -> range ~min:i (n - i)) in
  map [sequence xs] @@ fun js ->
    let arr = Array.copy arr in
    js |> List.iteri (fun i j ->
      let t = arr.(i) in
      arr.(i) <- arr.(j); arr.(j) <- t);
    arr

(The bias induced by mod doesn't matter here.)

[pqwy]

Ping @stedolan who merged while I was writing, lest the comments gets lost in github's torrent of activity :) .

[stedolan]

I'm happier with the version that generates an immutable list, even if it involves some copying (I have some experiments that share substructures of generated testcases, so generating mutable arrays scares me a bit). I like your map version better than the dynamic_bind version, though.

[pqwy]

Do you want a PR, then?

[NathanReb]

I'm not sure I get the first point since the current version already uses an array internally to shuffle. Whether it is then copied to a list or an array is just a matter of preferences and I'm guessing people will use lists more often than arrays.

[NathanReb]

Ok you're actually suggesting to pass it an array instead of a list to save the first copy.

[pqwy]

The first point is minor. It's just that shuffling an array is clearly the primitive operation here, so why not expose it as such? Otherwise, shuffling arrays is array->list->array->shuffle->list->array, and shuffling, say, my third sequence type is seq->list->array->shuffle->list->seq.

The major point is dropping the monad.

[stedolan]

PR for the map version welcome! I do prefer the list version, though: I don't care much about the copy and I'd like to avoid mutable structures in the API.