F # Math Libraries - Calculate Median

Question

I was wondering if anyone knows about Microsoft (or another library) to calculate the median of an array / list / sequence of integers in F #. I see an average function, but not median.

Thanks in advance,

In JP

Answer 1

Pick up where @Brian and @BrokenGlass stopped ...

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)

Below is a link describing the average O (n) algorithm with a C # implementation.

Answer 2

What about

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

? (Coding in the browser, any errors are mine.)

Answer 3

, .NET.

Here is the quickselect implementation . He expected time O (n) and worst time O (n ² ). The only type limitation 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 calls in such a way that it resembled a simple recursive call; Instead, let x, y = f a b; bodyI used f a b (fun x y -> body). This could be simplified a bit with 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)