haskell - 如何使用 State monad 计算 Haskell 列表中偶数的个数？

Question

我试图通过构建自己的示例来理解 Haskell 中 State Monad 的一些基础知识。

考虑一个简单的例子，我想计算一个整数数组中偶数的个数。当然这可以使用纯函数很容易地完成，但我想尝试循环状态 monad 路线，我们保留一个计数器，该计数器为每个已检查的元素不断递增。

这是迄今为止我设法提出的部分(但显然是错误的)尝试。

import Control.Monad.State

f' :: [Int] -> State Int [Int]
f' []     = state (\s -> ([],s)) 
f' (x:xs) = if x `mod` 2 == 0 then state (\s -> ((x:xs), s+1)) -- how can I fix this line? 
            else f' xs

这段代码可以编译，但显然没有给出正确答案。那么我该如何修复此代码，以执行类似于以下 Python 代码的操作

counter = 0 # incremented when we encounter an even integer.
for elt in integer_list:
   if elt % 2 == 0 :
      counter = counter + 1 

Answer 1

另一个答案是从头开始构建一个实现。我认为也值得看到对现有代码进行最小的更改以使其变得合理。我们甚至会保留您现有的类型——尽管另一个答案建议对其进行更改，但我认为这是可以接受的(如果不是很好的话)。

在我看来，真正的问题在于您只在 if 的一个分支中进行了递归。我们真正想要的是递归当前元素是否为偶数。所以:

f' (x:xs) = do
    if x `mod` 2 == 0 then state (\s -> ((), s+1)) -- increase the count by one
                      else state (\s -> ((), s  )) -- don't increase the count by one
    rest <- f' xs -- compute the answer for the rest of the list
    return (x:rest) -- reconstruct the answer for the whole list

我们可以在 ghci 中检查它是否做了正确的事情:

> runState (f' [1..5]) 0
([1,2,3,4,5],2)

这只是让您的实现想法发挥作用所能做出的最小改变。

从那里，我会建议一些重构。首先，您对 state 的普遍使用是一种代码味道。我会用这种方式写出各种用途:

f' [] = return []
f' (x:xs) = do
    if x `mod` 2 == 0 then modify (+1) else return ()
    rest <- f' xs
    return (x:rest)

从这里开始，我将在条件语句中使用 even 函数，并注意到 when 函数实现了“执行某些操作或 return ()”操作。所以:

f' [] = return []
f' (x:xs) = do
    when (even x) (modify (+1))
    rest <- f' xs
    return (x:rest)

此外，我们实际上有一个组合器，用于对列表的每个元素运行单子(monad)操作；即 mapM。所以我们可以这样把上面的显式递归变成隐式递归:

f' xs = mapM (\x -> when (even x) (modify (+1)) >> return x) xs

最后，我认为函数返回它使用的列表有点奇怪。 unidiomatic，就其本身而言，正如之前的反对意见一样，但也许不是您想要的。如果事实证明您不打算在任何后续计算中使用结果列表，那么随手丢弃它会更有效；而 mapM_ 组合器就是这样做的。所以:

f' :: [Int] -> State Int ()
f' xs = mapM_ (\x -> when (even x) (modify (+1))) xs

在这一点上，我认为 f' 是您提出的想法的一个很好的实现。