如何改進haskell滾動和實現？

Question

我該如何改進下面的滾動實施？

type Buffer = State BufferState (Maybe Double) 
type BufferState = ([Double] , Int, Int) 

-- circular buffer  
buff :: Double -> Buffer 
buff newVal = do 
    (list, ptr, len) <- get 
    -- if the list is not full yet just accumulate the new value 
    if length list < len 
    then do 
     put (newVal : list , ptr, len) 
     return Nothing 
    else do 
     let nptr = (ptr - 1) `mod` len 
      (as,(v:bs)) = splitAt ptr list 
      nlist = as ++ (newVal : bs) 
     put (nlist, nptr, len) 
     return $ Just v 

-- create intial state for circular buffer 
initBuff l = ([] , l-1 , l) 

-- use the circular buffer to calculate a rolling sum 
rollSum :: Double -> State (Double,BufferState) (Maybe Double) 
rollSum newVal = do 
    (acc,bState) <- get 
    let (lv , bState') = runState (buff newVal) bState 
     acc' = acc + newVal 
    -- subtract the old value if the circular buffer is full 
    case lv of 
    Just x -> put (acc' - x , bState') >> (return $ Just (acc' - x)) 
    Nothing -> put (acc' , bState')  >> return Nothing 

test :: (Double,BufferState) -> [Double] -> [Maybe Double] -> [Maybe Double] 
test state [] acc = acc 
test state (x:xs) acc = 
    let (a,s) = runState (rollSum x) state 
    in test s xs (a:acc) 

main :: IO() 
main = print $ test (0,initBuff 3) [1,1,1,2,2,0] [] 

緩衝區使用狀態monad實現循環緩衝區。 rollSum再次使用State monad來跟蹤滾動總和值和循環緩衝區的狀態。

• 我怎麼能使這更優雅？
• 我想實現其他功能，如滾動平均值或差異，我可以做些什麼來簡化它？

謝謝！

編輯

我忘了提我使用的是循環緩衝區，因爲我打算使用上線和工藝更新的代碼，他們到達 - 因此需要記錄狀態。像

newRollingSum = update rollingSum newValue 

Answer 1

我還沒有設法破譯所有的代碼，但這裏是我將採取的解決這個問題的計劃。首先，該計劃的英文說明：

1. 我們需要窗戶進入長度n的啓動列表中的每個索引。
   1. 製作任意長度的窗口。
   2. 截斷長窗戶到長度n。
   3. 刪除最後的n-1這些，這將太短。
2. 對於每個窗口，合計條目。

這是我的第一個想法;對於長度爲三的窗戶，這是一個好方法，因爲步驟2在這麼短的列表上便宜。對於更長的窗戶，您可能需要一種替代方法，我將在下面討論;但是這種方法有利於它順利地推廣到除sum以外的其他功能。代碼可能是這樣的：

import Data.List 

rollingSums n xs 
    = map sum        -- add up the entries 
    . zipWith (flip const) (drop (n-1) xs) -- drop the last n-1 
    . map (take n)       -- truncate long windows 
    . tails        -- make arbitrarily long windows 
    $ xs 

如果你熟悉的「等式推理」的方式優化，你可能會看到，我們可以提高此功能的性能第一名：通過交換第一map和zipWith，我們可以生成一個具有相同行爲但具有map f . map g子項的函數，它可以被map (f . g)取代以獲得略少的分配。

不幸的是，對於大型n，這在內部循環中將n號碼加在一起;我們寧願簡單地在窗口的「前面」添加該值，並在「後面」減去該值。所以我們需要變得更加棘手。以下是一個新想法：我們將平行遍歷列表兩次，分開位置n。然後，我們將使用一個簡單的函數來獲得列表前綴的滾動總和（無界窗口長度），即scanl (+)，以將此遍歷轉換爲我們感興趣的實際總和。

rollingSumsEfficient n xs = scanl (+) firstSum deltas where 
    firstSum = sum (take n xs) 
    deltas = zipWith (-) (drop n xs) xs -- front - back 

有一個扭曲，這是從來沒有scanl返回一個空列表。所以如果你能夠處理短名單是很重要的，你會需要另一個方程來檢查這些。不要使用length，因爲這會在開始計算之前強制整個輸入列表進入內存 - 這是潛在的致命性能錯誤。相反，在上面的定義之上添加一條像這樣的線：

rollingSumsEfficient n xs | null (drop (n-1) xs) = [] 

我們可以在ghci中試試這兩個。你會發現，他們不相當具有相同的行爲，你的：

*Main> rollingSums 3 [10^n | n <- [0..5]] 
[111,1110,11100,111000] 
*Main> rollingSumsEfficient 3 [10^n | n <- [0..5]] 
[111,1110,11100,111000] 

在另一方面，實現是相當多的非常簡潔，但在這個意義上完全懶，他們在無限列表的工作：

*Main> take 5 . rollingSums 10 $ [1..] 
[55,65,75,85,95] 
*Main> take 5 . rollingSumsEfficient 10 $ [1..] 
[55,65,75,85,95]