// Mean, over real numbers. The FLOAT version rounds; this one does not. function Sum(x: seq): real { if |x| == 0 then 0.0 else Sum(x[..|x| - 1]) + x[|x| - 1] } method Mean(x: seq) returns (m: real) requires |x| > 0 ensures m == Sum(x) / (|x| as real) { var total := 0.0; var i := 0; while i < |x| invariant 0 <= i <= |x| invariant total == Sum(x[..i]) { assert x[..i + 1][..i] == x[..i]; total := total + x[i]; i := i + 1; } assert x[..|x|] == x; m := total / (|x| as real); } // Every value at most hi: the sum is at most |x| * hi. lemma SumAtMost(x: seq, hi: real) requires forall i :: 0 <= i < |x| ==> x[i] <= hi ensures Sum(x) <= (|x| as real) * hi { if |x| > 0 { SumAtMost(x[..|x| - 1], hi); } } // Every value at least lo: the sum is at least |x| * lo. lemma SumAtLeast(x: seq, lo: real) requires forall i :: 0 <= i < |x| ==> lo <= x[i] ensures (|x| as real) * lo <= Sum(x) { if |x| > 0 { SumAtLeast(x[..|x| - 1], lo); } } // In exact arithmetic the mean lies between any lower and upper bound of the values. lemma MeanBetween(x: seq, lo: real, hi: real) requires |x| > 0 requires forall i :: 0 <= i < |x| ==> lo <= x[i] <= hi ensures lo <= Sum(x) / (|x| as real) <= hi { SumAtMost(x, hi); SumAtLeast(x, lo); }