遞歸狀態monad用於在構建列表時累積值？

對於Haskell來說，我是全新的，所以如果問題很愚蠢，請大家道歉。遞歸狀態monad用於在構建列表時累積值？

我想要做的是遞歸建立一個列表，而在同一時間建立一個基於遞歸調用的累計值。這是我爲Coursera課程所做的一個問題，所以我不會發布確切的問題，但類似的東西。

例如說我想採取INTS的列表和雙每一個（忽略的例子的目的，我可以只使用map），但我也想計數多少次數「 5'出現在列表中。

所以做了一倍我可以這樣做：

foo []  = [] 
foo (x:xs) = x * 2 : foo xs

到目前爲止那麼容易。但是我怎樣才能保持x是五次的次數呢？我已經得到了最好的解決方法是使用顯式蓄能器這樣的，我不喜歡，因爲它顛倒了列表，所以你需要在最後做一個反向：

foo total acc []  = (total, reverse acc) 
foo total acc (x:xs) = foo (if x == 5 then total + 1 else total) (x*2 : acc) xs

但我覺得這應該可以通過State monad更好地處理，我之前沒有用過，但是當我嘗試構建一個適合我看到的模式的函數時，由於遞歸調用foo而卡住了。有沒有更好的方法來做到這一點？

編輯：我需要這個工作很長的列表，所以任何遞歸調用也需要尾遞歸。（由於Haskell的'tail recursion modulo cons'，我在這裏的例子設法是尾遞歸的）。

來源

2013-07-07 Russell

相關的問題：「尾巴優化保障 - 在Haskell循環編碼」（http://stackoverflow.com/q/9149183/ 849891）。 –

您的示例尾遞歸在什麼意義上？我認爲它積聚了沉重，並導致「內存泄漏」。甚至簡單地調用'reverse'似乎足以導致內存泄漏。 – yairchu

當我說*它是*尾遞歸時，我的意思是簡單的地圖示例，而不是第二個代碼片段。 TBH我很難確定什麼是Haskell中的高效代碼，它看起來和我用過的其他語言完全不同。認爲我需要做更多的閱讀:-) – Russell

這是一個簡單摺疊

foo :: [Integer] -> ([Integer], Int) 
foo []  = ([], 0) 
foo (x : xs) = let (rs, n) = foo xs 
       in (2 * x : rs, if x == 5 then n + 1 else n)

或表達使用foldr

foo' :: [Integer] -> ([Integer], Int) 
foo' = foldr f ([], 0) 
    where 
    f x (rs, n) = (2 * x : rs, if x == 5 then n + 1 else n)

的累計值是一對兩個操作。

注：

看一看Beautiful folding。它顯示瞭如何使這種計算可組合的一個很好的方法。
通過查看每個元素爲有狀態計算，您也可以使用State作爲同樣的事情。這有點矯枉過正，但一定可行。事實上，任何褶皺可以被表達爲State計算的序列：
```
import Control.Monad 
import Control.Monad.State 

-- I used a slightly non-standard signature for a left fold 
-- for simplicity. 
foldl' :: (b -> a -> a) -> a -> [b] -> a 
foldl' f z xs = execState (mapM_ (modify . f) xs) z 
```
功能通過modify . f :: b -> State a()mapM_第一地圖的xs每個元素有狀態計算。然後它將這樣的計算列表合併成State a()（它丟棄單子計算的結果，只是保持效果）類型之一。最後我們在z上運行這個有狀態計算。

來源

2013-07-07 13:38:00

這種構造是否會尾遞歸？在遞歸調用之後肯定會做一些工作。我知道Haskell做了一些聰明的優化 - 是這個嗎？ – Russell

@Russell不，它不是尾遞歸的，有其原因。首先，這種方式更加懶惰 - 您可以讀取映射列表的第一個元素，並且只消耗原始列表的第一個元素。大多數情況下，拖尾效應優於尾遞歸。其次，對於一個高效的尾遞歸解決方案，您必須從頭開始使用該列表，但從結尾開始構建結果。所以如果你做了一個尾遞歸的'map'，它會顛倒這個列表。（如果你不關心訂單，這可能會有用。） –

我有一種感覺，這裏缺少一些爆炸模式。 :) –

使用State單子也可以是這樣的：

foo :: [Int] -> State Int [Int] 
foo [] = return [] 
foo (x:xs) = do 
    i <- get 
    put $ if x==5 then (i+1) else i 
    r <- foo xs 
    return $ (x*2):r 

main = do 
    let (lst,count) = runState (foo [1,2,5,6,5,5]) 0 in 
     putStr $ show count

來源

2013-07-07 17:12:01 Ankur

謝謝，此答案已幫助我瞭解了國家monad的工作原理......至少有一點點。 – Russell

遞歸狀態monad用於在構建列表時累積值？

回答

相關問題