递归状态monad用于在构建列表时累积值？

Question

如果问题很愚蠢的话,我对Haskell完全不熟悉.

我想要做的递归是建立一个列表,而在同一时间建立的累计值基础上的递归调用.这是我正在为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

但我觉得这应该能够被Statemonad 处理得更好,我之前没有用过,但是当我尝试构建一个适合我看到的模式的函数时,我会因为递归调用而陷入困境foo.有没有更好的方法来做到这一点？

编辑:我需要这个工作很长的列表,所以任何递归调用也需要尾递归.(由于Haskell的'tail recursion modulo cons',我在这里的例子设法是尾递归的).

Answer 1

使用Statemonad可以是这样的:

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

Answer 2

这是一个简单的折叠

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)

累计值是一对操作.

笔记:

• 看看美丽的折叠.它展示了如何使这种计算可组合的好方法.

• 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
  

  函数mapM_首先将每个元素映射xs到有状态计算modify . f :: b -> State a ().然后它将这样的计算列表组合成一个类型State a ()(它丢弃monadic计算的结果,只保留效果).最后我们运行这个有状态计算z.