haskell - 为什么第一个 Haskell 函数无法处理无限列表，而第二个代码段在无限列表中成功？

Question

我有两个 Haskell 函数，这两个函数对我来说都非常相似。但是第一个对无限列表失败，第二个对无限列表成功。我已经尝试了几个小时来确切地确定为什么会这样，但无济于事。

这两个片段都是 Prelude 中“单词”功能的重新实现。两者都适用于有限列表。

这是不处理无限列表的版本:

myWords_FailsOnInfiniteList :: String -> [String]
myWords_FailsOnInfiniteList string = foldr step [] (dropWhile charIsSpace string)
   where 
      step space ([]:xs)      | charIsSpace space = []:xs    
      step space (x:xs)       | charIsSpace space = []:x:xs
      step space []           | charIsSpace space = []
      step char (x:xs)                            = (char : x) : xs
      step char []                                = [[char]] 

这是处理无限列表的版本:

myWords_anotherReader :: String -> [String]
myWords_anotherReader xs = foldr step [""] xs
   where 
      step x result | not . charIsSpace $ x = [x:(head result)]++tail result
                    | otherwise             = []:result

注意:“charIsSpace”只是对 Char.isSpace 的重命名。

下面的解释器 session 说明第一个对无限列表失败，而第二个成功。

*Main> take 5 (myWords_FailsOnInfiniteList  (cycle "why "))
*** Exception: stack overflow

*Main> take 5 (myWords_anotherReader (cycle "why "))
["why","why","why","why","why"]

编辑:感谢下面的回复，我相信我现在明白了。以下是我的结论和修改后的代码:

结论:

我第一次尝试的最大罪魁祸首是两个以“step space []”和“step char []”开头的方程。 将阶跃函数的第二个参数与 [] 匹配是不可以的 ，因为它强制对整个第二个 arg 进行评估(但有一个警告要在下面解释)。

有一次，我认为 (++) 可能会以某种方式比 cons 更晚评估其右侧参数。所以，我想我可以通过将“= (char:x):xs”更改为“= [char : x]++ xs”来解决这个问题。但那是 不正确 .

有一次，我认为将第二个 arg 与 (x:xs) 匹配的模式会导致该函数对无限列表失败。我几乎是正确的，但不完全正确!针对 (x:xs) 评估第二个 arg，就像我在上面的模式匹配中所做的那样，将导致一些递归。它会“转动曲柄”，直到碰到“:”(又名“缺点”)。如果那从来没有发生过，那么我的函数将不会在无限列表中成功。但是，在这种特殊情况下，一切正常，因为我的函数最终会遇到一个空格，此时会出现“缺点”。由匹配 (x:xs) 触发的评估将在那里停止，避免无限递归。那时，“x”将被匹配，但 xs 将保持一个 thunk，所以没有问题。 (感谢 Ganesh 真正帮助我掌握了这一点)。

一般来说，您可以提只要你不想要第二个参数 力评价吧 .如果您已匹配 x:xs，那么您可以随心所欲地提及 xs，只要您不强制对其进行评估。

所以，这是修改后的代码。我通常尽量避免使用 head 和 tail，仅仅因为它们是部分函数，​​也因为我需要练习编写模式匹配等价物。

myWords :: String -> [String]
myWords string = foldr step [""] (dropWhile charIsSpace string)
   where 
      step space acc | charIsSpace space = "":acc
      step char (x:xs)                   = (char:x):xs
      step _ []                          = error "this should be impossible"

这正确地适用于无限列表。请注意，看不到头、尾或 (++) 运算符。

现在，重要的警告:
当我第一次编写更正后的代码时，我没有第三个等式，它与“step _ []”相匹配。结果，我收到了关于非详尽模式匹配的警告。显然，避免该警告是个好主意。

但我以为我会遇到问题。我已经在上面提到过将第二个 arg 与 [] 进行模式匹配是不行的。但我必须这样做才能摆脱警告。

但是，当我添加“step _ []”等式时，一切都很好!无限列表仍然没有问题! .为什么？

因为更正后的代码中的第三个方程从未达到!

实际上，请考虑以下 BROKEN 版本。它与正确的代码完全相同，只是我已将空列表的模式移到其他模式之上:

myWords_brokenAgain :: String -> [String]
myWords_brokenAgain string = foldr step [""] (dropWhile charIsSpace string)
   where 
      step _ []                              = error "this should be impossible"
      step space acc | charIsSpace space     = "":acc
      step char (x:xs)                       = (char:x):xs

我们回到堆栈溢出，因为调用 step 时发生的第一件事是解释器检查第一个等式是否匹配。为此，它必须查看第二个 arg 是否为 []。为此，它必须评估第二个参数。

将等式向下移动到其他等式下方可确保永远不会尝试第三个等式，因为第一个或第二个模式始终匹配。第三个方程只是为了免除非详尽的模式警告。

这是一次很棒的学习经历。感谢大家的帮助。

Answer 1

其他人已经指出了这个问题，即 step 总是在产生任何输出之前评估它的第二个参数，但是当 foldr 应用于无限列表时，它的第二个参数最终将取决于另一个 step 调用的结果。

它不一定要这样写，但是你的第二个版本有点难看，因为它依赖于初始参数来步进具有特定格式，并且很难看出头部/尾部永远不会出错。 (我什至不能 100% 确定他们不会!)

您应该做的是重构第一个版本，以便它至少在某些情况下生成输出而不依赖于输入列表。特别是我们可以看到，当字符不是空格时，输出列表中总是至少有一个元素。因此，将第二个参数的模式匹配延迟到生成第一个元素之后。字符是空格的情况仍然取决于列表，但这很好，因为这种情况可以无限递归的唯一方法是传入一个无限的空格列表，在这种情况下不产生任何输出并进入循环是单词的预期行为(它还能做什么？)