使用fold计算平均值

Question

如何使用map和reduce计算数字列表的平均值。

理想情况下，我想在列表上调用reduce并得到一个平均值。您可以选择首先对该列表进行映射和过滤。

以下是一个LISP示例：

(defun average (list)
  (reduce ... list))

一个简单的JS代码框架：

function average (array) {
  return array.reduce(function() {
    ..
  }, 0);
}

如果你用某种语言发布了一个带有实际代码的答案，请把它解释得像我是那种语言的初学者一样（我很可能就是）。我希望避免那些琐碎的回答。

function average (array) {
   return sum(array) / array.length;
}

这里使用的是除法而不是reduce语句。我认为这是“作弊”。

[[编辑]]

我解决了自己的问题。如果有人使用LISP或Haskell的语法糖拥有优雅的解决方案，我会很感兴趣。

- Raynos

---

也许更适合于 CodeGolf.SE？ - ircmaxell

一个简单的reduce（也称为fold）并不是mapreduce（例如Google框架）。即使您事先对输入进行了map，也不是。 - user395760

@delnan 抱歉，我混淆了术语。 - Raynos

第一步应该是计算出解决方案背后的数学。你能想到一个迭代算法来得到你想要的结果吗？将其转化为“fold”应该不会太难。 - abesto

@abesto，现在解决方案看起来非常简单。我当时没想到，谢谢。 - Raynos

Answer 1

如@abesto所提到的，这需要一个迭代算法。

Let counter be 0 
For each [value, index] in list   
  let sum be (counter * index) + value   
  let counter be sum / (index + 1)

return counter

JavaScript 实现将会是：

var average = function(list) { 
    // returns counter
    return list.reduce(function(memo, val, key) {
         // memo is counter
         // memo * key + val is sum. sum / index is counter, counter is returned
         return ((memo * key) + val) / (key + 1)
    // let counter be 0
    }, 0);  
}

- Raynos

Answer 2

使用map和reduce计算数列的平均值没有必要，只需要使用unfold生成列表，再使用fold将其缩减为平均值即可：

mean n m = uncurry (/) . foldr g (0, 0) . unfoldr f $ n
      where 
        f b | b > m     = Nothing
            | otherwise = Just (b, b+1)

        g x (s,n) = (s+x, n+1)

一个高效的实现

这个结构（fold . unfold）允许进行融合优化。特别有效的实现将会将生成列表的unfold与列表约简的fold融合在一起。在Haskell中，GHC通过流融合组合了这两个阶段（unfold == enumFromN）和fold：

import Data.Vector.Unboxed 

data Pair = Pair !Int !Double

mean :: Vector Double -> Double
mean xs = s / fromIntegral n
  where
    Pair n s       = foldl' k (Pair 0 0) xs
    k (Pair n s) x = Pair (n+1) (s+x)

main = print (mean $ enumFromN 1 (10^7))

编译器将两个函数组合成一个递归循环：

main_loop a d e n =
    case ># a 0 of 
      False -> (# I# n, D# e #);
      True -> main_loop (-# a 1) (+## d 1.0) (+## e d) (+# n 1)

这将在汇编语言中转换为goto（编译器的C后端）：

Main_mainzuzdszdwfoldlMzqzuloop_info:
        leaq    32(%r12), %rax
        cmpq    %rax, 144(%r13)
        movq    %r12, %rdx
        movq    %rax, %r12
        jb      .L198
        testq   %r14, %r14
        jle     .L202
.L199:
        movapd  %xmm5, %xmm0
        leaq    -1(%r14), %r14
        movsd   .LC0(%rip), %xmm5
        addq    $1, %rsi
        addsd   %xmm0, %xmm6
        movq    %rdx, %r12
        addsd   %xmm0, %xmm5
        jmp     Main_mainzuzdszdwfoldlMzqzuloop_info

使用LLVM可以得到更高效但更加复杂的实现（速度大约快2倍）。

---

参考资料: 在Haskell中高效计算列表平均值

- Don Stewart

Answer 3

这是一个Common Lisp版本：

(defun running-avg (r v)
  (let* ((avg (car r))
         (weight (cdr r))
         (new-weight (1+ weight)))
    (cons (/ (+ (* avg weight) v) new-weight) new-weight)))

(car (reduce 'running-avg '(3 6 5 7 9) :initial-value '(0 . 0)))
;; evaluates to 6

它跟踪运行平均值和权重，并计算新平均值为((先前的平均值 * 权重) + 新值)。

- ataylor

---

你能解释一下 1+ 和 weight 吗？我对 LISP 一无所知。还有 * (car r) (cdr r)，r 是元组吗？ - Raynos

1+是将参数加1的函数。weight只是一个本地变量名称。是的，r是一个元组；我通过创建一些有意义的名称来整理了它。 - ataylor

“:initial-value” 的作用相当明显，但你能解释一下这个语法的语义吗？ - Raynos

这是 reduce 函数的一个可选关键字参数。Common Lisp 函数可以接受命名参数，其中名称是 Lisp 符号。前导冒号只是 Lisp 符号的语法表示。使用初始值时，函数的第一次调用是 (initial-value, element0) 而不是 (element0, element1)。 - ataylor

现在我理解了这段代码，我更喜欢原始版本，因为它具有经典的LISP简洁性 :) - Raynos

Answer 4

一种Haskell方法的描述，它允许对折叠进行组合式处理： http://conal.net/blog/posts/another-lovely-example-of-type-class-morphisms/

- sclv

---

如果我参加了“Haskell初学者课程”，那篇文章就会有意义。 - Raynos

链接的“美丽折叠”帖子更易于访问。 - sclv

Answer 5

在Mathematica中

mean[l_List]:=
    Fold[{First@#1+1,(#2 +#1[[2]](First@#1-1))/First@#1}&,{1,1},l][[2]]  

In[23]:= mean[{a,b,c}]
Out[23]= 1/3 (a+b+c)

- Dr. belisarius