Haskell、Monads、堆栈空间、惰性——如何构造惰性代码？

Question

一个人为的示例，但下面的代码演示了我在学习 Haskell 时不断遇到的一类问题。

import Control.Monad.Error
import Data.Char (isDigit)

countDigitsForList [] = return []
countDigitsForList (x:xs) = do
    q  <- countDigits x
    qs <- countDigitsForList xs
    return (q:qs)

countDigits x = do
    if all isDigit x
        then return $ length x
        else throwError $ "Bad number: " ++ x

t1 = countDigitsForList ["1", "23", "456", "7890"] :: Either String [Int]
t2 = countDigitsForList ["1", "23", "4S6", "7890"] :: Either String [Int]

t1 给了我正确的答案，t2 正确识别了错误。

在我看来，对于足够长的列表，此代码将耗尽堆栈空间，因为它在 monad 内部运行，并且在每个步骤中它都会在返回结果之前尝试处理列表的其余部分。

累加器和尾递归似乎可以解决问题，但我反复读到，由于惰性求值，这两者在 Haskell 中都是不必要的。

如何将这种代码构造成不会出现堆栈空间问题和/或懒惰的代码？

Answer 1

How do I structure this kind of code into one which won't have a stack space problem and/or be lazy?

你不能让这个函数懒惰地处理列表，无论是否有 monad。以下是 countDigitsForList 的直接翻译，使用模式匹配而不是 do 表示法:

countDigitsForList [] = return []
countDigitsForList (x:xs) = case countDigits x of
    Left e  -> Left e
    Right q -> case countDigitsForList xs of
                   Left e   -> Left e
                   Right qs -> Right (q:qs)

这里应该更容易看出，因为列表中任何一点的 Left 都会使整个列表返回该值，为了确定结果的最外层构造函数，整个列表必须被遍历和处理；同样地处理每个元素。因为最终结果可能取决于最后一个字符串中的最后一个字符，所以编写的这个函数本质上是严格的，就像对数字列表求和一样。

鉴于此，要做的事情是确保函数足够严格，以避免构建巨大的未计算表达式。想要了解这方面的信息，最好从讨论 foldr、foldl 和 foldl' 之间的差异开始。

An accumulator and tail recursion seems like it may solve the problem but I repeatedly read that neither are necessary in Haskell because of lazy evaluation.

当您可以延迟生成、处理和使用列表时，两者都是不必要的；最简单的例子是map。对于不可能做到这一点的函数，严格评估的尾递归正是您想要的。