Вычисления среднего из списка эффективно в Haskell

Ваше решение хорошее, использование двух функций не хуже, чем одной. Тем не менее, вы могли бы поместить хвостовую рекурсивную функцию в предложение where.

Но если вы хотите сделать это в одной строке:

calcMeanList = uncurry (/) . foldr (\e (s,c) -> (e+s,c+1)) (0,0)

Лучшее, что вы можете сделать, это эту версию :

import qualified Data.Vector.Unboxed as U

data Pair = Pair {-# UNPACK #-}!Int {-# UNPACK #-}!Double

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

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

Она сливается с оптимальным циклом в Core (лучший Haskell, который вы могли написать):

main_$s$wfoldlM'_loop :: Int#
                              -> Double#
                              -> Double#
                              -> Int#
                              -> (# Int#, Double# #)    
main_$s$wfoldlM'_loop =
  \ (sc_s1nH :: Int#)
    (sc1_s1nI :: Double#)
    (sc2_s1nJ :: Double#)
    (sc3_s1nK :: Int#) ->
    case ># sc_s1nH 0 of _ {
      False -> (# sc3_s1nK, sc2_s1nJ #);
      True ->
        main_$s$wfoldlM'_loop
          (-# sc_s1nH 1)
          (+## sc1_s1nI 1.0)
          (+## sc2_s1nJ sc1_s1nI)
          (+# sc3_s1nK 1)
    }

И следующую сборку:

Main_mainzuzdszdwfoldlMzqzuloop_info:
.Lc1pN:
        testq %r14,%r14
        jg .Lc1pQ
        movq %rsi,%rbx
        movsd %xmm6,%xmm5
        jmp *(%rbp)
.Lc1pQ:
        leaq 1(%rsi),%rax
        movsd %xmm6,%xmm0
        addsd %xmm5,%xmm0
        movsd %xmm5,%xmm7
        addsd .Ln1pS(%rip),%xmm7
        decq %r14
        movsd %xmm7,%xmm5
        movsd %xmm0,%xmm6
        movq %rax,%rsi
        jmp Main_mainzuzdszdwfoldlMzqzuloop_info

По материалам Data.Vector. Например,

$ ghc -Odph --make A.hs -fforce-recomp
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...
$ time ./A
5000000.5
./A  0.04s user 0.00s system 93% cpu 0.046 total

См. Эффективные реализации в статистическом пакете .

Когда я увидел ваш вопрос, я сразу подумал: «Вы хотите фолд там!»

И, конечно же, аналогичный вопрос уже задавался ранее на StackOverflow, и этот ответ имеет очень производительное решение, которое вы можете протестировать в интерактивной среде, такой как GHCi:

import Data.List

let avg l = let (t,n) = foldl' (\(b,c) a -> (a+b,c+1)) (0,0) l 
            in realToFrac(t)/realToFrac(n)

avg ([1,2,3,4]::[Int])
2.5
avg ([1,2,3,4]::[Double])
2.5

Для тех, кому интересно узнать, как будет выглядеть подход светового кодера и Ассафа в Haskell, вот один перевод:

avg [] = 0
avg x@(t:ts) = let xlen = toRational $ length x
                   tslen = toRational $ length ts
                   prevAvg = avg ts
               in (toRational t) / xlen + prevAvg * tslen / xlen

Этот способ гарантирует, что на каждом шаге будет правильно вычислено «среднее на данный момент», но это будет происходить за счет целой кучи избыточного умножения / деления на длину и очень неэффективных вычислений длины на каждом шаге. Ни один опытный Хаскеллер не стал бы так писать.

Только немного лучший способ:

avg2 [] = 0
avg2 x = fst $ avg_ x
    where 
      avg_ [] = (toRational 0, toRational 0)
      avg_ (t:ts) = let
           (prevAvg, prevLen) = avg_ ts
           curLen = prevLen + 1
           curAvg = (toRational t) / curLen + prevAvg * prevLen / curLen
        in (curAvg, curLen)

Это позволяет избежать повторного вычисления длины. Но для этого требуется вспомогательная функция, а именно ее пытается избежать исходный постер. И это по-прежнему требует отмены слишком длинных сроков.

Чтобы избежать сокращения длин, мы можем просто построить сумму и длину и разделить в конце:

avg3 [] = 0
avg3 x = (toRational total) / (toRational len)
    where 
      (total, len) = avg_ x
      avg_ [] = (0, 0)
      avg_ (t:ts) = let 
          (prevSum, prevLen) = avg_ ts
       in (prevSum + t, prevLen + 1)

И это можно гораздо более кратко записать в виде foldr:

avg4 [] = 0
avg4 x = (toRational total) / (toRational len)
    where
      (total, len) = foldr avg_ (0,0) x
      avg_ t (prevSum, prevLen) = (prevSum + t, prevLen + 1)

, который можно упростить как согласно сообщениям выше.

Фолд - действительно правильный выбор.

Хотя я не уверен, было бы «лучше» записать его в одной функции, это можно сделать следующим образом:

Если вы знаете длину (давайте назовем ее здесь 'n') заранее это просто - вы можете подсчитать, сколько каждое значение «прибавляет» к среднему; это будет значение / длина. Поскольку avg (x1, x2, x3) = sum (x1, x2, x3) / length = (x1 + x2 + x3) / 3 = x1 / 3 + x2 / 3 + x2 / 3

Если вы не знаю заранее длину, это немного сложнее:

допустим, мы используем список {x1, x2, x3} , не зная его n = 3.

первая итерация будет просто x1 (поскольку мы предполагаем, что ее только n = 1) вторая итерация добавит x2 / 2 и разделит существующее среднее на 2, так что теперь у нас есть x1 / 2 + x2 / 2

, после третьей итерации у нас n = 3, и мы хотели бы чтобы иметь x1 / 3 + x2 / 3 + x3 / 3 , но у нас есть x1 / 2 + x2 / 2

, поэтому нам нужно будет умножить на (n-1) и разделим на n , чтобы получить x1 / 3 + x2 / 3 , и к этому мы просто добавляем текущее значение (x3), разделенное на n, чтобы получить x1 / 3 + x2 / 3 + x3 / 3

Обычно:

с учетом среднего (среднее арифметическое - avg) для n-1 элементов, если вы хотите добавить один элемент (newval) к среднему значению, ваше уравнение будет быть:

средн * (n-1) / n + newval / n . Уравнение может быть доказано математически с помощью индукции.

Надеюсь, это поможет.

* обратите внимание, что это решение менее эффективно, чем простое суммирование переменных и деление на общую длину, как в вашем примере.