8

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

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

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

4

2 回答 2

11

使用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
于 2013-07-07T17:12:01.580 回答
8

这是一个简单的折叠

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 ()（它丢弃一元计算的结果，只保留效果）。最后，我们在 上运行这个有状态的计算z。

于 2013-07-07T13:38:00.907 回答