Implement array element swap in a functional language Sorting algorithms involve swapping element positions in an array. This is my implementation of swap:

let swap (array: 'a[]) (first: int) (second: int): 'a[] = 
    let originalFirst = array.[first]
    array.[first] &lt;- array.[second];
    array.[second] &lt;- originalFirst;
    array


Though it works, I am wondering whether mutating an array is canonical F#. If not, what is the canonical way to swap array element positions? 

The F# documentation says that arrays are mutable. Am I misunderstanding immutability?

Any and all comments on the above implementation are most welcome.
First and foremost: while mutation may be generally frowned upon in F#, in some cases (like this one) it's acceptable to make a tradeoff of immutability vs. performance or maintainability. In this case, it serves both of those goals.

Let's say you want to do this idiomatically, and you want to avoid directly mutating the array. It isn't that hard:

let swap el1 el2 arr =
    arr |&gt; Array.mapi (fun i v -&gt;
        match i with
        | _ when i = el1 -&gt; arr.[el2]
        | _ when i = el2 -&gt; arr.[el1]
        | _ -&gt; v)


This uses the mapi function, which provides the current index and value (in that order, defined by the int -&gt; 'T -&gt; 'U signature) which we can then match with our el1 (first element to swap) and el2 (second element to swap). If we hit either of those simply return the other element.

But then, this isn't enough. What if we have several pairs to swap? We have to call swap a1 b1 arr then a swap a2 b2 arr, which could have a substantial performance penalty.

We could define a swapMany function which would take a list of tuples which are the first and second elements to swap and then handle them.

let swapMany els arr =
    arr |&gt; Array.mapi (fun i v -&gt;
        match els |&gt; List.tryFind (fun el -&gt;
            match el with
            | (el1, el2) when el1 = i || el2 = i -&gt; true
            | _ -&gt; false) with
        | Some (el1, el2) when el1 = i -&gt; arr.[el2]
        | Some (el1, el2) when el2 = i -&gt; arr.[el1]
        | _ -&gt; v)


Now we handle all the swaps in one pass. If they're ordered, then the cost is even lower.

let values = [|1..10|]
let value =
    values
    |&gt; swapMany [(4, 8); (2, 5)]


Result:


[|1; 2; 6; 4; 9; 3; 7; 8; 5; 10|]



But we're still not done, let's say we want to write our swapMany such that it doesn't create the entire result array, we want to stream it, sort of like an IEnumerable in C#.

In F# this isn't nearly as hard as it seems, all we have to do here is rewrite our swapMany as a sequence generator, which turns it into:

let swapMany els arr =
    seq {
        for i in 0..(Array.length arr - 1) -&gt;
            match els |&gt; List.tryFind (fun el -&gt;
                match el with
                | (el1, el2) when el1 = i || el2 = i -&gt; true
                | _ -&gt; false) with
            | Some (el1, el2) when el1 = i -&gt; arr.[el2]
            | Some (el1, el2) when el2 = i -&gt; arr.[el1]
            | _ -&gt; arr.[i]
    }


Now, you might say "why would I want to write a sequence generator for an array?" Consider you have a huge array:

let values = [|1..100000000|]


And you want to swapMany on it, but you're then going to enumerate the array for the first 10 values:

let value =
    values
    |&gt; swapMany [(4, 8); (20, 50)]
printfn "%A" (value |&gt; Seq.take 10 |&gt; Seq.toArray)


You don't have to swap everything in the array now, you just have to swap the elements you need.



Second, the only issue I see with your code is the order of arguments. When writing functions it's nice to be able to use the pipe-right operator (|&gt;) to push the left value as a parameter to the function on the right. In the case of your function, if I were to try to pipe an array to the right, it won't work. This is because the pipe-right (or pipe-forward) operator pipes the left side as the last argument to the right side.


let swap (array: 'a[]) (first: int) (second: int): 'a[] = 
    let originalFirst = array.[first]
    array.[first] &lt;- array.[second];
    array.[second] &lt;- originalFirst;
    array

[|1..10|] |&gt; swap 4 5



The above code is invalid, because the argument 4 is expected to be the 'a[] array, and the argument 5 is the first int, and the array [|1..10|] is expected to be the second int argument.

let swap (first: int) (second: int) (array: 'a[]): 'a[] = 
    let originalFirst = array.[first]
    array.[first] &lt;- array.[second];
    array.[second] &lt;- originalFirst;
    array

[|1..10|] |&gt; swap 4 5


F# also includes a double-forward-pipe and triple-forward-pipe operator, which do the same thing but pipe a tuple of either two or three values, respectively, to the right side as the last two or three arguments, respectively.

Consider an example:

let append str1 str2 str3 = str1 + "." + str2 + "." + str3
printfn "%s" ("ghi" |&gt; append "abc" "def")
printfn "%s" (("def", "ghi") ||&gt; append "abc")
printfn "%s" (("abc", "def", "ghi") |||&gt; append)


All three of the printfn statements will print abc.def.ghi.

You can see more of this looking through the framework. You'll see that most functions in List and Seq take the list or sequence as the last parameter, so that you can pipe the result of one function to another.

Consider how much more painful the following code would have been to write had the framework designers chosen to not take this factor into account:


let values = [1..100]
let value =
    values
    |&gt; List.map (fun v -&gt; Math.Sin(float v))
    |&gt; List.choose (fun v -&gt; if v &gt;= 0.0 then Some v else None)
    |&gt; List.rev
    |&gt; List.takeWhile (fun v -&gt; v &gt; 0.05)
    |&gt; List.fold (fun v acc -&gt; acc + v) 0.0
printfn "%f" value