F# Math Libraries - Calculate Median [closed]

开发者_C百科 As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 10 years ago.

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

---

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.

---

How about

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

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

---

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)