使用折叠的平均值

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; 
} 

琐碎回答这个在最终用途划分而不是一个减少声明。我认为这是“作弊”。

[编辑]

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

Answer 1

下面是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 

它跟踪一个跑步大道愤怒和体重，并计算新的平均值为((previous average * weight) + new value)。

Answer 2

由于@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); 
} 

Answer 3

哈斯克尔的apporach的描述，允许进行组成方式折叠： http://conal.net/blog/posts/another-lovely-example-of-type-class-morphisms/

Answer 4

计算使用地图号码列表的平均值，并减少

有没有map需要。就在展开生成列表，折叠将其降低到平均值：

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）允许发生融合优化。一个特别有效的实现将融合展开（列表生成）与折叠（列表缩减）。在此，在Haskell，GHC结合了两个相（展开== enumFromN），并通过流融合的折叠：

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的速度（约快两倍）。

---

参考：Computing the mean of a list efficiently in Haskell

Answer 5

在数学

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)