F# Math Libraries - Calculate Median

Question

I was wondering if anyone knows of a Microsoft (or other library) for calculating the median of an array/list/sequence of integers in F#. I see an Average function, but no median.

Thanks in advance,

JP

Answer 1

Picking up where @Brian and @BrokenGlass left off...

let inline median input = 
    let sorted = input |> Seq.toArray |> Array.sort
    let m1,m2 = 
        let len = sorted.Length-1 |> float
        len/2. |> floor |> int, len/2. |> ceil |> int 
    (sorted.[m1] + sorted.[m2] |> float)/2.

//by marking the function inline, we gain some extra flexibility with static member constraints
//val inline median :
//  seq< ^a> -> float
//    when  ^a : comparison and  ^a : (static member ( + ) :  ^a *  ^a ->  ^b) and
//          ^b : (static member op_Explicit :  ^b -> float)

(kinda makes me long for implicit conversions between numeric types)

Here's a link describing an on average O(n) algorithm with a C# implementation.

Answer 2

How about

let a = input |> Seq.toArray |> Array.sort
a.[a.Length / 2]

? (Coding in a browser, any mistakes are mine.)

Answer 3

If you absolutely want a library, you could look at this question, or look for other questions about statistics libraries on .NET.

Here is an implementation of quickselect. It has expected time O(n) and worst-case time O(n²). The only restriction on the type is that they are comparable.

/// Calculate the median of a list of items.
/// The result is a tuple of two items whose mean is the median.
let median xs =
    /// Partition list into three piles; less-than, equal and greater-than
    /// x:    Current pivot
    /// xs:   Sublist to partition
    /// cont: Continuation function
    let rec partition x xs cont =
        match xs with
        | [] ->
            // place pivot in equal pile
            cont [] 0 [x] 1 [] 0
        | y::ys ->
            if y < x then
                // place item in less-than pile
                partition x ys (fun lts n1 eqs n2 gts n3 ->
                    cont (y::lts) (n1+1) eqs n2 gts n3)
            elif y = x then
                // place pivot in equal pile, and use item as new pivot,
                // so that the order is preserved
                partition y ys (fun lts n1 eqs n2 gts n3 ->
                    cont lts n1 (x::eqs) (n2+1) gts n3)
            else // y > x
                // place item in greater-than pile
                partition x ys (fun lts n1 eqs n2 gts n3 ->
                    cont lts n1 eqs n2 (y::gts) (n3+1))
    /// Partition input and recurse into the part than contains the median
    /// before: Number of elements before this sublist.
    /// xs:     Current sublist.
    /// after:  Number of elements after this sublist.
    let rec loop before xs after =
        match xs with
        | [] -> failwith "Median of empty list"
        | x::xs ->
            partition x xs (fun lts numlt eqs numeq gts numgt ->
                if before + numlt > numeq + numgt + after then
                    // Recurse into less pile
                    loop before lts (after + numeq + numgt)
                elif before + numlt = numeq + numgt + after then
                    // Median is split between less and equal pile
                    (List.max lts, x)
                elif before + numlt + numeq > numgt + after then
                    // Median is completely inside equal pile
                    (x, x)
                elif before + numlt + numeq = numgt + after then
                    // Median is split between equal and greater pile
                    (x, List.min gts)
                else
                    // Recurse into greater pile
                    loop (before + numlt + numeq) gts after)
    loop 0 xs 0

I used continuations to make it tail-recursive. I tried to write the calls in such a way that it resembles a simple recursive call; Instead of let x, y = f a b; body I used f a b (fun x y -> body). It could be simplified a little with the CPS monad.

Example:

> median [1];;
val it : int * int = (1, 1)
> median [1;2];;
val it : int * int = (1, 2)
> median [1..9];;
val it : int * int = (5, 5)