recursion - 递归计算列表平均值

Question

我有 OCaml 作业要做，其中一个问题是计算列表的平均值。我在 1 或 2 年前已经用另一种语言做到了，就像我第一次做的那样，我决定不仅对所有元素求和并除以长度。主要原因是担心 float 溢出。

所以我在维基百科上找到了我上次使用的公式:recursive average formula .

我在 OCaml 中是这样编码的:

let average = function
| []    -> raise Empty_list
| hd::l ->
    let rec aux average count = function
        | hd::l -> aux ((average*.(float (count-1))+.hd)/.(float (count))) (count+1) l
        | _     -> average
    in aux hd 1 l
;;

对我来说，这看起来像是 OCaml 中公式的精确转录。

但是它没有用，但是，在拿了一张纸，一支笔并考虑了一下之后，我设法通过更换行使其工作:

| hd::l -> aux ((average*.(float (count-1))+.hd)/.(float (count))) (count+1) l

与:

| hd::l -> aux ((average*.(float (count))+.hd)/.(float (count+1))) (count+1) l

它奏效了。

我告诉自己，第二行在逻辑上是计算正确答案的好方法，但我不明白一开始哪里出了问题。我是否翻译了有偏见的公式？还是我翻译的时候遗漏了什么？

此时，它仍然在寻找我，第一行是公式的转录，第二行是计算正确答案的方式。但我相信这里有一些我无法理解的东西。有人可以为我阐明这一点吗？

Answer 1

作为引用，这里是一个不会以正确的时间复杂度溢出的函数版本:

let avg l =
  let mu_n' (n,mu_n) x =
    let n' = n + 1 in
    n', mu_n +. (x -. mu_n) /. float n' in
  snd (List.fold_left mu_n' (0,0.) l)

let x = avg [max_float; 1.; 2.; max_float;2.; 3.; max_float; 5.; 6.]
let relative_error = (x -. max_float /. 3.) /. (max_float /. 3.)

val relative_error : float = -1.66533453693773481e-16