Haskell,Monads,Stack Space,Laziness - 如何构造代码变得懒惰？

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

如何将这种代码构造成一个没有堆栈空间问题和/或懒惰的代码？

你不能让这个函数懒惰地处理列表,monads或no.这是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'.

累加器和尾递归似乎可以解决问题,但我反复阅读,由于懒惰的评估,在Haskell中都没有必要.

当您可以懒惰地生成,处理和使用列表时,两者都是不必要的; 这里最简单的例子就是map.对于无法实现的功能,严格评估的尾递归正是您想要的.

Answer 2

camccann是正确的,该功能本质上是严格的.但这并不意味着它不能以恒定的堆栈运行!

countDigitsForList xss = go xss []
    where go (x:xs) acc = case countDigits x of
                             Left e -> Left e
                             Right q -> go xs (q:acc)
          go [] acc = reverse acc

这个累积参数版本是camccann代码的部分cps变换,我打赌你也可以通过cps转换后的monad来获得相同的结果.

编辑考虑到jwodder对逆转的纠正.哎呀.正如John L所指出的那样,隐含或明确的差异列表也会起作用......