# Get MAD with Outliers with an Improved Median Function

This post presents a more robust method of detecting outliers in sample data than commonly used. The method is based on the median and an optimised F# median function is developed.

## Background

Researchers most commonly use standard deviation around the mean to detect outliers. This is a problem because the mean and standard deviation give greater weight to extreme data points.

The mean is the point that minimises the sum of the square deviations, whereas the median is the point that minimises the sum of the absolute deviations. The median and median absolute deviation give a more robust measure of statistical dispersion and are more resilient to outliers.

When a politician says average wages are increasing be sure to check the median is being reported.

## Median Absolute Deviation

The median is the value separating the higher half of the sample from the lower half.

The median absolute deviation is defined as

$\operatorname{MAD} = \operatorname{median}\left(\left|x_i - \operatorname{median}(x_i)\right|\right)$

Outliers can be identified as points that are outside a fixed multiple of the median absolute deviation from the median. Recommended values for this multiple are 2.5 or 3.

The following median function makes use of the MODIFIND algorithm by Vladimir Zabrodsky. It provides a 20-30% performance improvement over the Quickselect algorithm.

The array while loops allow equality which improves performance when there is duplication and ordering in the data. The selectInPlace function has also been extended to optionally return the middle of the kth and the k+1 element.

module Statistics =
/// Returns the median of three input values.
let inline median3 a b c =
if a<=b then
if b<=c then b
elif c<=a then a
else c
else
if a<=c then a
elif c<=b then b
else c
/// Returns the minimum value of a subsection of an array.
let inline minSub (a:_[]) lo hi =
let mutable v = a.[lo]
for i = lo+1 to hi do
let nv = a.[i]
if nv<v then v<-nv
v
/// Returns the maximum value of a subsection of an array.
let inline maxSub (a:_[]) lo hi =
let mutable v = a.[lo]
for i = lo+1 to hi do
let nv = a.[i]
if nv>v then v<-nv
v
/// Returns the middle point of the two smallest values of a subsection of an array.
let inline min2middleSub (a:_[]) lo hi =
let mutable v0 = a.[lo]
let mutable v1 = a.[lo+1]
if v1<v0 then
let tmp = v0
v0<-v1
v1<-tmp
for i = lo+2 to hi do
let nv = a.[i]
if nv<v0 then
v1<-v0
v0<-nv
elif nv<v1 then
v1<-nv
middleOrdered v0 v1
/// Returns the middle point of the two largest values of a subsection of an array.
let inline max2middleSub (a:_[]) lo hi =
let mutable v0 = a.[lo]
let mutable v1 = a.[lo+1]
if v1>v0 then
let tmp = v0
v0<-v1
v1<-tmp
for i = lo+2 to hi do
let nv = a.[i]
if nv>v0 then
v1<-v0
v0<-nv
elif nv>v1 then
v1<-nv
middleOrdered v1 v0
/// Swap two elements in an array.
let inline swap (a:_[]) i j =
let temp = a.[i]
a.[i]<-a.[j]
a.[j]<-temp
/// Swap two elements in an array if the first is larger than the second.
let inline swapIf (a:_[]) i j =
let ai = a.[i]
let aj = a.[j]
if ai>aj then
a.[i]<-aj
a.[j]<-ai
/// Returns the kth smallest element in an array and optionally the middle with
/// the next largest. Elements will be reordered in place and cannot be equal
/// to the max or min value of the generic type.
let inline selectInPlace (a:_[]) k middleNext =
let rec outerLoop lo hi =
swapIf a lo k
swapIf a lo hi
swapIf a k hi
let pivot = a.[k]
let resetLo = if a.[lo]=pivot then a.[lo]<-minValue(); true else false
let resetHi = if a.[hi]=pivot then a.[hi]<-maxValue(); true else false
let mutable i = lo+1
let mutable j = hi-1
while a.[i]<=pivot do i<-i+1
while a.[j]>=pivot do j<-j-1
while i<k && k<j do
swap a i j
i<-i+1
j<-j-1
while a.[i]<=pivot do i<-i+1
while a.[j]>=pivot do j<-j-1
if i<j then
swap a i j
if k<j then
i<-lo
j<-j-1
while a.[j]>=pivot do j<-j-1
else
j<-hi
i<-i+1
while a.[i]<=pivot do i<-i+1
else
if k<j then i<-lo
elif k>i then j<-hi
if resetLo then a.[lo]<-pivot
if resetHi then a.[hi]<-pivot
if i>=j then if middleNext then if k+1=i then
minSub a i hi |> middleOrdered pivot
else pivot
else pivot
elif k=i then if middleNext then min2middleSub a i j else minSub a i j
elif k=j then if middleNext then max2middleSub a i j else maxSub a i j
else outerLoop i j
outerLoop 0 (Array.length a-1)
/// Returns the median of an array. Elements will be reordered in place and
/// cannot be equal to the max or min value of the generic type.
let inline medianInPlace (a:_[]) =
match Array.length a-1 with
| 0 -> a.[0]
| 1 -> middle a.[0] a.[1]
| 2 -> median3 a.[0] a.[1] a.[2]
| last -> selectInPlace a (last/2) (last%2=1)
/// Returns the median and median absolute deviation of an array.
/// Elements cannot be equal to the max or min value of the generic type.
let a = Array.copy a
let median  = medianInPlace a
for i = 0 to Array.length a-1 do
a.[i]<-abs(a.[i]-median)
median,medianInPlace a


## Property and Performance testing

A simple FsCheck property test comparing the result with a full sort version ensures no mistakes have been made in the implementation.

The performance versus a full sort algorithm and the Math.Net C# Quickselect implementation are compared for different degrees of duplication and sorting.

The performance testing library developed in a previous post is used after extending it to allow subfunction measurement. This is run from the build script in 64-bit Release mode.

module StatisticsTests =
let inline medianQuickSelect (a:float[]) =
MathNet.Numerics.Statistics.ArrayStatistics.MedianInplace a

let inline medianFullSort a =
Array.sortInPlace a
let l = Array.length a
if l%2=0 then
let i = l/2
let x = a.[i-1]
let y = a.[i]
x+(y-x)*0.5
else a.[l/2]

[<Property>]
let MedianProp (x:int) (xs:int list) =
let l = x::xs |> List.map float
let m1 = List.toArray l |> Statistics.medianInPlace
let m2 = List.toArray l |> medianFullSort
m1=m2

type Duplication =
| Low | Medium | High
member i.ToInt = match i with | Low->500000000 | Medium->5000 | High->50
override i.ToString() =
match i with | Low->"Low" | Medium->"Medium" | High->"High"

type Sorted =
| No | Part | Yes
override i.ToString() = match i with | No->"No" | Part->"Part" | Yes->"Yes"

let list (duplication:Duplication) (sorted:Sorted) =
let r = System.Random 123
let next() = r.Next(0,duplication.ToInt) |> float
Seq.init 5000 (fun i ->
let l = List.init (i+1) (fun _ -> next())
match sorted with
| No -> l
| Yes -> List.sort l
| Part ->
let a = List.sort l |> List.toArray
let len = Array.length a
Seq.iter (fun _ -> Statistics.swap a (r.Next len) (r.Next len))
{1..len/4}
List.ofArray a
)

[<Fact>]
let MedianPerfTest() =
"| Duplication |   Sorted   |  Current  |  MathNet  |  FullSort  |  1.000 =  |"
|> printfn
"|:-----------:|:----------:|:---------:|:---------:|:----------:|:---------:|"
|> printfn
Seq.collect (fun d -> Seq.map (fun s -> (d,s),list d s) [No;Part;Yes])
[Low;Medium;High]
|> Seq.iter (fun ((d,s),lists) ->
let timeStatistics f =
Performance.timeStatistics
(fun timer -> Seq.iter (List.toArray >> timer f >> ignore) lists)
let p1 = timeStatistics Statistics.medianInPlace
let p2 = timeStatistics medianQuickSelect
let p3 = timeStatistics medianFullSort
printfn
"|    %-6s   |    %-4s    |   1.000   |  %6.3f   |   %6.3f   |  %.4fs  |"
(string d) (string s) (p2.Mean/p1.Mean) (p3.Mean/p1.Mean) p1.Mean
)


Duplication

Sorted

Current

MathNet

FullSort

1.000 =

Low

No

1.000

1.369

6.582

0.1028s

Low

Part

1.000

1.350

9.269

0.0476s

Low

Yes

1.000

1.516

12.964

0.0106s

Medium

No

1.000

1.373

6.577

0.1018s

Medium

Part

1.000

1.397

9.471

0.0478s

Medium

Yes

1.000

1.840

17.519

0.0100s

High

No

1.000

1.341

4.745

0.1059s

High

Part

1.000

1.576

8.050

0.0526s

High

Yes

1.000

3.193

26.390

0.0087s

## Conclusion

Optimised generic select, median and median absolute deviation functions have been developed.

The performance results show a good improvement over Quickselect which is already an optimised algorithm. The performance of the code is also more predictable due to its handling of duplication and partially sorted data.

This also demonstrates how property based testing and a performance testing library can be used together to optimise algorithms.

namespace System
namespace System.Diagnostics
type PropertyAttribute = | FactAttribute
union case PropertyAttribute.FactAttribute: PropertyAttribute
Multiple items
type AutoOpenAttribute =
inherit Attribute
new : unit -> AutoOpenAttribute
new : path:string -> AutoOpenAttribute
member Path : string

--------------------
new : unit -> AutoOpenAttribute
new : path:string -> AutoOpenAttribute
val sqr : x:'a -> 'b (requires member ( * ))
val x : 'a (requires member ( * ))
Multiple items
union case MinValueGen.MinValueGen: MinValueGen

--------------------
type MinValueGen =
| MinValueGen
static member ( => ) : MinValueGen * int -> int
static member ( => ) : MinValueGen * int64 -> int64
static member ( => ) : MinValueGen * float -> float
static member ( => ) : MinValueGen * MinValueGen -> 'a
Multiple items
val int : value:'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int
type Int32 =
struct
member CompareTo : value:obj -> int + 1 overload
member Equals : obj:obj -> bool + 1 overload
member GetHashCode : unit -> int
member GetTypeCode : unit -> TypeCode
member ToString : unit -> string + 3 overloads
static val MaxValue : int
static val MinValue : int
static member Parse : s:string -> int + 3 overloads
static member TryParse : s:string * result:int -> bool + 1 overload
end
field int.MinValue: int = -2147483648
Multiple items
val int64 : value:'T -> int64 (requires member op_Explicit)

--------------------
type int64 = Int64

--------------------
type int64<'Measure> = int64
type Int64 =
struct
member CompareTo : value:obj -> int + 1 overload
member Equals : obj:obj -> bool + 1 overload
member GetHashCode : unit -> int
member GetTypeCode : unit -> TypeCode
member ToString : unit -> string + 3 overloads
static val MaxValue : int64
static val MinValue : int64
static member Parse : s:string -> int64 + 3 overloads
static member TryParse : s:string * result:int64 -> bool + 1 overload
end
field int64.MinValue: int64 = -9223372036854775808L
Multiple items
val float : value:'T -> float (requires member op_Explicit)

--------------------
type float = Double

--------------------
type float<'Measure> = float
type Double =
struct
member CompareTo : value:obj -> int + 1 overload
member Equals : obj:obj -> bool + 1 overload
member GetHashCode : unit -> int
member GetTypeCode : unit -> TypeCode
member ToString : unit -> string + 3 overloads
static val MinValue : float
static val MaxValue : float
static val Epsilon : float
static val NegativeInfinity : float
static val PositiveInfinity : float
...
end
field float.MinValue: float = -1.79769313486e+308
val failwith : message:string -> 'T
val minValue : unit -> 'a (requires member get_Zero and member ( => ))

Returns the minimum value for a generic type.
module LanguagePrimitives

from Microsoft.FSharp.Core
val GenericZero<'T (requires member get_Zero)> : 'T (requires member get_Zero)
Multiple items
union case MaxValueGen.MaxValueGen: MaxValueGen

--------------------
type MaxValueGen =
| MaxValueGen
static member ( => ) : MaxValueGen * int -> int
static member ( => ) : MaxValueGen * int64 -> int64
static member ( => ) : MaxValueGen * float -> float
static member ( => ) : MaxValueGen * MaxValueGen -> 'a
field int.MaxValue: int = 2147483647
field int64.MaxValue: int64 = 9223372036854775807L
field float.MaxValue: float = 1.79769313486e+308
val maxValue : unit -> 'a (requires member get_Zero and member ( => ))

Returns the maximum value for a generic type.
Multiple items
union case HalfPositiveGen.HalfPositiveGen: HalfPositiveGen

--------------------
type HalfPositiveGen =
| HalfPositiveGen
static member ( => ) : HalfPositiveGen * x:int -> int
static member ( => ) : HalfPositiveGen * x:int64 -> int64
static member ( => ) : HalfPositiveGen * x:float -> float
static member ( => ) : HalfPositiveGen * HalfPositiveGen -> 'a
val x : int
val x : int64
val x : float
val halfPositive : x:'a -> 'a (requires member ( => ))

Returns half of the positive generic input value.
val x : 'a (requires member ( => ))
val middleOrdered : a:'a -> b:'c -> 'd (requires member ( + ) and member ( - ) and member ( => ))

Returns the middle point of two ordered input values.
val a : 'a (requires member ( + ) and member ( - ) and member ( => ))
val b : 'c (requires member ( - ) and member ( + ) and member ( => ))
val middle : a:'a -> b:'a -> 'c (requires comparison and member ( + ) and member ( - ) and member ( => ))

Returns the middle point of two input values.
val a : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val b : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
SampleStatistics.N: int
SampleStatistics.Mean: float
SampleStatistics.Variance: float
val s : SampleStatistics
val sqrt : value:'T -> 'U (requires member Sqrt)
type WelchStatistic =
{T: float;
DF: int;}
WelchStatistic.T: float
WelchStatistic.DF: int
val sampleStatistics : s:seq<'a> -> seq<SampleStatistics> (requires member op_Explicit)

Online statistics sequence for a given sample sequence.
val s : seq<'a> (requires member op_Explicit)
val calc : (int * float * float -> float -> int * float * float)
val n : int
val m : float
val s : float
val m' : float
module Seq

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>
val scan : folder:('State -> 'T -> 'State) -> state:'State -> source:seq<'T> -> seq<'State>
val skip : count:int -> source:seq<'T> -> seq<'T>
val scale : f:float -> s:SampleStatistics -> SampleStatistics

Scale the statistics for a given underlying random variable change of scale.
val f : float
val singleIteration : ic:int -> s:SampleStatistics -> SampleStatistics

Single iteration statistics for a given iteration count and total statistics.
val ic : int
val private tInv : float []

Student's t-distribution inverse for 0.1% confidence level by degrees of freedom.
val welchStatistic : s1:SampleStatistics -> s2:SampleStatistics -> WelchStatistic

Welch's t-test statistic for two given sample statistics.
val s1 : SampleStatistics
val s2 : SampleStatistics
val f1 : float
val f2 : float
val welchTest : w:WelchStatistic -> int

Welch's t-test for a given Welch statistic to a confidence level of 0.1%.
val w : WelchStatistic
val abs : value:'T -> 'T (requires member Abs)
type Array =
member Clone : unit -> obj
member CopyTo : array:Array * index:int -> unit + 1 overload
member GetEnumerator : unit -> IEnumerator
member GetLength : dimension:int -> int
member GetLongLength : dimension:int -> int64
member GetLowerBound : dimension:int -> int
member GetUpperBound : dimension:int -> int
member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
member Initialize : unit -> unit
member IsFixedSize : bool
...
val get : array:'T [] -> index:int -> 'T
val min : e1:'T -> e2:'T -> 'T (requires comparison)
val length : array:'T [] -> int
val sign : value:'T -> int (requires member get_Sign)
module StatisticsPerf

from Main
val private targetIterationCount : metric:(int -> 'a -> 'b) -> metricTarget:'b -> f:'a -> int (requires member ( <<< ) and comparison and member op_Explicit)

Find the iteration count to get to at least the metric target.
val metric : (int -> 'a -> 'b) (requires member ( <<< ) and comparison and member op_Explicit)
val metricTarget : 'b (requires member ( <<< ) and comparison and member op_Explicit)
val f : 'a
val find : (int -> int)
val item : 'b (requires member ( <<< ) and comparison and member op_Explicit)
val private measureStatistics : metric:(int -> 'a -> 'b) * metricTarget:'b -> relativeError:float -> f:'a -> SampleStatistics (requires member ( <<< ) and comparison and member op_Explicit and member op_Explicit)

Create and iterate a statistics sequence for a metric until the given accuracy.
val metric : (int -> 'a -> 'b) (requires member ( <<< ) and comparison and member op_Explicit and member op_Explicit)
val metricTarget : 'b (requires member ( <<< ) and comparison and member op_Explicit and member op_Explicit)
val relativeError : float
val initInfinite : initializer:(int -> 'T) -> seq<'T>
val find : predicate:('T -> bool) -> source:seq<'T> -> 'T
property SampleStatistics.MeanStandardError: float
val private measureCompare : metric:(int -> (('a -> 'a) -> 'b) -> 'c) * metricTarget:'c -> f1:(('a -> 'a) -> 'b) -> f2:(('a -> 'a) -> 'b) -> int (requires equality and member ( <<< ) and comparison and member op_Explicit and member op_Explicit)

Create and iterate two statistics sequences until the metric means can be compared.
val metric : (int -> (('a -> 'a) -> 'b) -> 'c) (requires equality and member ( <<< ) and comparison and member op_Explicit and member op_Explicit)
val metricTarget : 'c (requires member ( <<< ) and comparison and member op_Explicit and member op_Explicit)
val f1 : (('a -> 'a) -> 'b) (requires equality)
val f2 : (('a -> 'a) -> 'b) (requires equality)
val id : x:'T -> 'T
val stats : ((('a -> 'a) -> 'b) -> seq<SampleStatistics>) (requires equality)
val f : (('a -> 'a) -> 'b) (requires equality)
val map2 : mapping:('T1 -> 'T2 -> 'U) -> source1:seq<'T1> -> source2:seq<'T2> -> seq<'U>
val pick : chooser:('T -> 'U option) -> source:seq<'T> -> 'U
val maxDF : int
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
val c : int
val private measureMetric : startMetric:(unit -> 'a) -> endMetric:('a -> 'b) -> ic:int -> f:((('d -> 'e) -> 'd -> 'e) -> 'f) -> 'c (requires member ( + ) and member get_Zero)

Measure the given function for the iteration count using the start and end metric.
val startMetric : (unit -> 'a)
val endMetric : ('a -> 'b) (requires member ( + ) and member get_Zero)
val f : ((('d -> 'e) -> 'd -> 'e) -> 'f)
type GC =
static member AddMemoryPressure : bytesAllocated:int64 -> unit
static member CancelFullGCNotification : unit -> unit
static member Collect : unit -> unit + 4 overloads
static member CollectionCount : generation:int -> int
static member EndNoGCRegion : unit -> unit
static member GetGeneration : obj:obj -> int + 1 overload
static member GetTotalMemory : forceFullCollection:bool -> int64
static member KeepAlive : obj:obj -> unit
static member MaxGeneration : int
static member ReRegisterForFinalize : obj:obj -> unit
...
GC.Collect() : unit
GC.Collect(generation: int) : unit
GC.Collect(generation: int, mode: GCCollectionMode) : unit
GC.Collect(generation: int, mode: GCCollectionMode, blocking: bool) : unit
GC.Collect(generation: int, mode: GCCollectionMode, blocking: bool, compacting: bool) : unit
GC.WaitForPendingFinalizers() : unit
val mutable total : 'c (requires member get_Zero and member ( + ))
val measurer : (('g -> 'h) -> 'g -> 'h)
val toMeasure : ('g -> 'h)
val args : 'g
val s : 'a
val ret : 'h
val m : 'b (requires member ( + ) and member get_Zero)
val loop : (int -> unit)
val i : int
val ignore : value:'T -> unit
val private timeMetric : ic:int -> f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int64

Measure the time metric for the given function and iteration count.
val f : ((('a -> 'b) -> 'a -> 'b) -> 'c)
Multiple items
type Stopwatch =
new : unit -> Stopwatch
member Elapsed : TimeSpan
member ElapsedMilliseconds : int64
member ElapsedTicks : int64
member IsRunning : bool
member Reset : unit -> unit
member Restart : unit -> unit
member Start : unit -> unit
member Stop : unit -> unit
static val Frequency : int64
...

--------------------
Stopwatch() : Stopwatch
Stopwatch.GetTimestamp() : int64
val t : int64
val private memoryMetric : ic:int -> f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int64

Measure the memory metric for the given function and iteration count.
val startMetric : (unit -> int64)
GC.TryStartNoGCRegion(totalSize: int64) : bool
GC.TryStartNoGCRegion(totalSize: int64, disallowFullBlockingGC: bool) : bool
GC.TryStartNoGCRegion(totalSize: int64, lohSize: int64) : bool
GC.TryStartNoGCRegion(totalSize: int64, lohSize: int64, disallowFullBlockingGC: bool) : bool
val not : value:bool -> bool
GC.GetTotalMemory(forceFullCollection: bool) : int64
val endMetric : (int64 -> int64)
val s : int64
GC.EndNoGCRegion() : unit
val private garbageMetric : ic:int -> f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int

Measure the garbage collection metric for the given function and iteration count.
val count : (unit -> int)
GC.CollectionCount(generation: int) : int
val s : int
val private oneMillisecond : int64

Measure definitions which are a metric together with a metric target.
field Stopwatch.Frequency: int64
val private timeMeasure : (int -> ((('a -> 'b) -> 'a -> 'b) -> 'c) -> int64) * int64
val private memoryMeasure : (int -> ((('a -> 'b) -> 'a -> 'b) -> 'c) -> int64) * int64
val private garbageMeasure : (int -> ((('a -> 'b) -> 'a -> 'b) -> 'c) -> int) * int
val timeStatistics : f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> SampleStatistics

Time statistics for a given function accurate to a mean standard error of 1%.
val memoryStatistics : f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> SampleStatistics

Memory statistics for a given function accurate to a mean standard error of 1%.
val gcCountStatistics : f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> SampleStatistics

GC count statistics for a given function accurate to a mean standard error of 1%.
val timeCompare : f1:((('a -> 'b) -> 'a -> 'b) -> 'c) -> f2:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int (requires equality)

Time comparison for two given functions to a confidence level of 0.1%.
val f1 : ((('a -> 'b) -> 'a -> 'b) -> 'c) (requires equality)
val f2 : ((('a -> 'b) -> 'a -> 'b) -> 'c) (requires equality)
val memoryCompare : f1:((('a -> 'b) -> 'a -> 'b) -> 'c) -> f2:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int (requires equality)

Memory comparison for two given functions to a confidence level of 0.1%.
val gcCountCompare : f1:((('a -> 'b) -> 'a -> 'b) -> 'c) -> f2:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int (requires equality)

GC count comparison for two given functions to a confidence level of 0.1%.
val median3 : a:'a -> b:'a -> c:'a -> 'a (requires comparison)

Returns the median of three input values.
val a : 'a (requires comparison)
val b : 'a (requires comparison)
val c : 'a (requires comparison)
val minSub : a:'a [] -> lo:int -> hi:int -> 'a (requires comparison)

Returns the minimum value of a subsection of an array.
val a : 'a [] (requires comparison)
val lo : int
val hi : int
val mutable v : 'a (requires comparison)
val nv : 'a (requires comparison)
val maxSub : a:'a [] -> lo:int -> hi:int -> 'a (requires comparison)

Returns the maximum value of a subsection of an array.
val min2middleSub : a:'a [] -> lo:int -> hi:int -> 'c (requires comparison and member ( + ) and member ( - ) and member ( => ))

Returns the middle point of the two smallest values of a subsection of an array.
val a : 'a [] (requires comparison and member ( + ) and member ( - ) and member ( => ))
val mutable v0 : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val mutable v1 : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val tmp : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val nv : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val max2middleSub : a:'a [] -> lo:int -> hi:int -> 'c (requires comparison and member ( + ) and member ( - ) and member ( => ))

Returns the middle point of the two largest values of a subsection of an array.
val swap : a:'a [] -> i:int -> j:int -> unit

Swap two elements in an array.
val a : 'a []
val j : int
val temp : 'a
val swapIf : a:'a [] -> i:int -> j:int -> unit (requires comparison)

Swap two elements in an array if the first is larger than the second.
val ai : 'a (requires comparison)
val aj : 'a (requires comparison)
val selectInPlace : a:'a [] -> k:int -> middleNext:bool -> 'a (requires comparison and member get_Zero and member ( => ) and member ( => ) and member ( - ) and member ( + ) and member ( => ))

Returns the kth smallest element in an array and optionally the middle with
the next largest. Elements will be reordered in place and cannot be equal
to the max or min value of the generic type.
val a : 'a [] (requires comparison and member get_Zero and member ( => ) and member ( => ) and member ( - ) and member ( + ) and member ( => ))
val k : int
val middleNext : bool
val outerLoop : (int -> int -> 'a) (requires comparison and member get_Zero and member ( => ) and member ( => ) and member ( - ) and member ( + ) and member ( => ))
val pivot : 'a (requires comparison and member get_Zero and member ( => ) and member ( => ) and member ( - ) and member ( + ) and member ( => ))
val resetLo : bool
val resetHi : bool
val mutable i : int
val mutable j : int
val medianInPlace : a:'a [] -> 'a (requires comparison and member ( + ) and member ( - ) and member get_Zero and member ( => ) and member ( => ) and member ( => ))

Returns the median of an array. Elements will be reordered in place and
cannot be equal to the max or min value of the generic type.
val a : 'a [] (requires comparison and member ( + ) and member ( - ) and member get_Zero and member ( => ) and member ( => ) and member ( => ))
val last : int
val medianAndMAD : a:'a [] -> 'a * 'a (requires comparison and member ( + ) and member get_Zero and member ( => ) and member ( => ) and member Abs and member ( - ) and member ( => ))

Returns the median and median absolute deviation of an array.
Elements cannot be equal to the max or min value of the generic type.
val a : 'a [] (requires comparison and member ( + ) and member get_Zero and member ( => ) and member ( => ) and member Abs and member ( - ) and member ( => ))
val copy : array:'T [] -> 'T []
val median : 'a (requires comparison and member ( + ) and member get_Zero and member ( => ) and member ( => ) and member Abs and member ( - ) and member ( => ))
module StatisticsTests

from Main
val medianQuickSelect : a:float [] -> 'a
val a : float []
val medianFullSort : a:float [] -> float
val sortInPlace : array:'T [] -> unit (requires comparison)
val l : int
val y : float
val MedianProp : x:int -> xs:int list -> bool
val xs : int list
type 'T list = List<'T>
val l : float list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member GetSlice : startIndex:int option * endIndex:int option -> 'T list
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
...
val map : mapping:('T -> 'U) -> list:'T list -> 'U list
val m1 : float
val toArray : list:'T list -> 'T []
module Statistics

from Main
val m2 : float
union case Duplication.Low: Duplication
union case Duplication.Medium: Duplication
union case Duplication.High: Duplication
val i : Duplication
union case Sorted.No: Sorted
union case Sorted.Part: Sorted
union case Sorted.Yes: Sorted
val i : Sorted
Multiple items
val list : duplication:Duplication -> sorted:Sorted -> seq<float list>

--------------------
type 'T list = List<'T>
val duplication : Duplication
type Duplication =
| Low
| Medium
| High
override ToString : unit -> string
member ToInt : int
val sorted : Sorted
type Sorted =
| No
| Part
| Yes
override ToString : unit -> string
val r : Random
Multiple items
type Random =
new : unit -> Random + 1 overload
member Next : unit -> int + 2 overloads
member NextBytes : buffer:byte[] -> unit
member NextDouble : unit -> float

--------------------
Random() : Random
Random(Seed: int) : Random
val next : (unit -> float)
Random.Next() : int
Random.Next(maxValue: int) : int
Random.Next(minValue: int, maxValue: int) : int
property Duplication.ToInt: int
val init : count:int -> initializer:(int -> 'T) -> seq<'T>
val init : length:int -> initializer:(int -> 'T) -> 'T list
val sort : list:'T list -> 'T list (requires comparison)
val len : int
val iter : action:('T -> unit) -> source:seq<'T> -> unit
val ofArray : array:'T [] -> 'T list
val MedianPerfTest : unit -> unit
val printfn : format:Printf.TextWriterFormat<'T> -> 'T
val collect : mapping:('T -> #seq<'U>) -> source:seq<'T> -> seq<'U>
val d : Duplication
val s : Sorted
val lists : seq<float list>
val timeStatistics : ((float [] -> 'a) -> SampleStatistics)
val f : (float [] -> 'a)
module Performance

from Main
val timer : ((float [] -> 'a) -> float [] -> 'a)
val p1 : SampleStatistics
val p2 : SampleStatistics
val p3 : SampleStatistics
Multiple items
val string : value:'T -> string

--------------------
type string = String