haskell - 用于在构建列表时累积值的递归状态单子(monad)？

Question

我对 Haskell 完全陌生，如果这个问题很愚蠢，我深表歉意。

我想要做的是递归地建立一个列表，同时建立一个基于递归调用的累积值。这是针对我正在为 Coursera 类(class)做的一个问题，所以我不会发布确切的问题，而是发布类似的问题。

例如，我想获取一个整数列表并将每个整数加倍(出于示例的目的，我可以只使用 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'，我这里的例子是尾递归的)。

Answer 1

使用 State monad 它可以是这样的:

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