F# Random Permutation. Split und Shuffle.

von Rosetta Code Knuth shuffle.

let KnuthShuffle (lst : array<'a>) =
    let Swap i j =                                                 
        let item = lst.[i]
        lst.[i] <- lst.[j]
        lst.[j] <- item
    let rnd = new System.Random()
    let ln = lst.Length
    [0..(ln - 2)]                                                   
    |> Seq.iter (fun i -> Swap i (rnd.Next(i, ln)))  // swap the item at the index with a random one following it (or itself)
    lst

let shuffle = KnuthShuffle [|0..1000|]

Wie man sieht verwendet dieser Code Wertzuweisungen ("side effect"), da die Array-Elemente geändert werden.
Ich fragte mich, wie implementiert man so eine Algorithmus in der funktionalen Programmierung und bin hier findig geworden. Da ist es ausführlich mit Beispiel in Haskell erklärt.
Hier ist mein Versuch in F#. Erstmal die Split-Funktion für die Listen.

let splitAt n=
    let rec splitAtRec acc n l =
        match n, l with
        |0, xs       -> (fst acc, xs)
        |_, []       -> ([], [])
        |n, x :: xs -> splitAtRec (x::fst acc, snd acc) (n-1) xs
    splitAtRec ([],[]) n

Was wichtig ist, dass die Funktion "tail recursive" ist.

let ran = new System.Random()
let mergeRandom l1 l2 =
    let lengthAndList l = (List.length l),l
    
    let rec merge acc (nx,xs) (ny, ys) =
        match (nx, xs), (ny, ys) with
        |(0 , []), (ny , ys)-> 
            match ys with
            |[h]-> h::acc
            |h::tl->
                ys@acc
            |_-> acc
        |(nx, xs), (0 , [])-> 
            match xs with
            |[h]->h::acc
            |h::tl->
                xs@acc
            |_-> acc
        |(_, x'::xs'), (_, y'::ys')-> 
            let random = ran.Next(1, nx + ny)
            if random <= nx then
                merge (x'::acc) (nx-1, xs') (ny, ys)
            else
                merge (y'::acc) (nx, xs) (ny-1, ys')
        |_->[]
    merge [] (lengthAndList l1) (lengthAndList l2)

let Shuffle =
    let rec mergeSort l =
        match l with
        |[] -> []
        |[x] -> [x]
        |l -> 
            let l1,l2 = splitAt (l.Length/2) l 
            mergeRandom (mergeSort l1) (mergeSort l2)
    mergeSort

Die Shuffle-Funktion ist nach meinem Verständnis nicht "tail recursive", also sollte es zu einem StackOverflow-Fehler kommen, aber bei mir hat der nicht aufgetreten.
Leider ist meine funktionale Version viel zu langsam.