How to shuffle list in O(n) in OCaml?

Question

It is not hard to shuffle an array in O(n), with in place swapping,

How to do it for list in OCaml, with O(n)?

---

Requirement:

1. No array or in place usage

2. Consider this as an interview question

Answer 1

Lists are immutable, and there's often a log n price to pay for working with immutable data. If you're willing to pay this cost, there's an obvious n log n approach: tag each list element with a random value, sort based on random value, remove random values. This is the way I shuffle lists in my production code.

Here is the shuffle code from the iOS apps that I sell:

let shuffle d =
    let nd = List.map (fun c -> (Random.bits (), c)) d in
    let sond = List.sort compare nd in
    List.map snd sond