我實作了以下函式：
iterateState :: Int -> (a -> State s a) -> （a -> State s [a])
iterateState 0 f a = return [] 。
iterateState n f a =do
b <- f a
xs <- iterateState (n - 1) f b
回傳 $ b : xs
我的主要用例是a = Double。它可以作業，但非常慢。它分配了528MB的堆空間來產生一個1M的Double值的串列，并將大部分時間用于垃圾回收。
我嘗試了一些實作，這些實作直接在型別s -> (a, s)上作業，以及使用各種嚴格性注釋。我能夠在一定程度上減少堆的分配，但是還沒有達到人們對一個合理的實作的期望。我懷疑所產生的([a], s)是一個被懶惰地消耗的東西（[a]）和一個其WWNF強制整個計算的東西（s）的組合，使得GHC難以優化。
假設串列的迭代特性不適合這種情況，我轉向了vector包。令我高興的是，它已經包含了
iterateNM :: (Monad m, Unbox a) => Int -> (a -> m a) -> a -> m （Vector a)
不幸的是，這只比我的串列實作稍快，仍然分配了328MB的堆空間。我認為這是因為它使用了unstreamM，它的描述是
將單體流捆綁到新分配的向量中。這個函式要經過一個串列，所以最好使用unstream，除非你需要在一個單體中。
看看它對串列單體的行為，可以理解為一般單體沒有有效的實作。幸運的是，我只需要狀態單體，而且我找到了另一個幾乎符合狀態單體簽名的函式。
unfoldrExactN :: Unbox a => Int -> (b -> (a, b)) -> b -> Vector a
這個函式的速度快得驚人，除了需要8MB來容納所產生的1M個Double值的非盒式向量外，沒有進行多余的堆分配。不幸的是，它在計算結束時沒有回傳最終的狀態，所以它不能被包裹在State型別中。
我查看了 unfoldrExactN 的實作，看看我是否可以調整它以在計算結束時暴露最終狀態。不幸的是，這似乎是困難的，因為由
unfoldrExactN :: Monad m => Int -> (s -> (a, s)) -> s -> Stream m a
最終被unstream擴展成一個向量，已經忘記了狀態型別s。
我想我可以繞過整個Stream基礎設施并在ST單體中的可變向量上直接實作iterateState（類似于unstream如何將流擴展為向量）。然而，我將失去流融合的所有好處，以及將一個很容易表達為純函式的計算變成僅僅出于性能原因的命令式低級混雜。這尤其令人沮喪，因為我知道現有的 unfoldrExactN 已經計算了我想要的所有值，但我卻無法訪問它們。
是否有更好的方法？
這個函式是否可以實作？
這個函式能否以純粹的功能方式實作，并具有合理的性能和沒有多余的堆分配？最好是以一種與vector包及其流融合基礎設施相聯系的方式。
uj5u.com熱心網友回復：
下面的程式在經過優化編譯后，在我的電腦上的最大駐留時間為12MB：
import Data.Vector.Unboxed
import Data.Vector.Unboxed.Mutable
iterateNState :: Unboxed a => Int -> (a -> s -> (s, a)) -> (a -> s -> (s, Vector a)
iterateNState n f a0 s0 = createT (unsafeNew n >>= go 0 a0 s0) where?
去 i a s arr
| i >= n = pure (s, arr)
| 否則=do
不安全的寫法 arr i a
case f a s of
(s', a') -> go (i 1) a' s' arr
main = id
. 列印
. Data.Vector.Unboxed.sum
.snd
$ iterateNState 1000000 (a s -> (s 1, a s :: Int) 00
(即使最后兩個0被動態地從輸入中讀取，它仍然有一個很好的低駐留率。)
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/316982.html
標籤：
上一篇：為什么我必須呼叫兩次"sum"來對一個"MaybeInteger"串列求和？
下一篇：for回圈函式回傳函式外