为什么第一个 Haskell 函数无法处理无限列表，而第二个片段却成功处理无限列表？

Question

我有两个 Haskell 函数，这两个函数对我来说都非常相似。 但是第一个在无限列表上失败了，第二个在无限列表上成功了。 我花了好几个小时试图弄清楚到底为什么会这样，但无济于事。

两个片段都是 Prelude 中“words”功能的重新实现。 两者都可以很好地处理有限列表。

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

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 的重命名。

以下解释器会话说明第一个解释器会话针对无限列表失败，而第二个解释器会话成功。

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

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

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

结论：

1. 我第一次尝试中最大的罪魁祸首是以“step space []”和“step char []”开头的两个方程。 将阶跃函数的第二个参数与 [] 相匹配是不允许的，因为它会强制评估整个第二个参数（但有一个警告将在下面解释）。
2. 在某一时刻，我曾认为 (++) 可能会以某种方式晚于 cons 评估其右侧参数。 所以，我想我可以通过将“ = (char:x):xs”更改为“= [char : x] ++ xs”来解决问题。 但这是不正确的。
3. 在某一时刻，我认为将第二个参数与 (x:xs) 匹配的模式会导致函数针对无限列表失败。 我关于这一点几乎是正确的，但不完全正确！ 正如我在上面的模式匹配中所做的那样，根据 (x:xs) 评估第二个参数，将导致一些递归。 它将“转动曲柄”直到碰到“：”（又名“cons”）。 如果这种情况从未发生过，那么我的函数将无法针对无限列表成功。 然而，在这种特殊情况下，一切都很好，因为我的函数最终会遇到空格，此时会出现“cons”。 并且由匹配 (x:xs) 触发的评估将立即停止，避免无限递归。 此时，“x”将被匹配，但 xs 仍将是一个 thunk，所以没有问题。 （感谢 Ganesh 真正帮助我理解了这一点）。
4. 一般来说，您可以提及您想要的第二个参数，只要您不强制评估它即可。 如果您已与 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 _ []”匹配的第三个方程。 结果，我收到了有关非详尽模式匹配的警告。 显然，避免该警告是个好主意。

但我以为我会遇到问题。 我上面已经提到不能将第二个参数与 [] 进行模式匹配。 但我必须这样做才能消除警告。

但是，当我添加“step_[]”方程时，一切都很好！ 无限列表仍然没有问题！。 为什么？

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

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

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 时发生的第一件事是解释器检查看看等式一是否匹配。 为此，它必须查看第二个参数是否为 []。 为此，它必须评估第二个参数。

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

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

Answer 1

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

它不必以这种方式编写，但您的第二个版本有点丑陋，因为它依赖于具有特定格式的步骤的初始参数，并且很难看出头/尾永远不会出错。 （我什至不能 100% 确定它们不会！）

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

Answer 2

尝试手动扩展表达式：

 take 5 (myWords_FailsOnInfiniteList  (cycle "why "))
 take 5 (foldr step [] (dropWhile charIsSpace (cycle "why ")))
 take 5 (foldr step [] (dropWhile charIsSpace ("why " ++ cycle "why ")))
 take 5 (foldr step [] ("why " ++ cycle "why "))
 take 5 (step 'w' (foldr step [] ("hy " ++ cycle "why ")))
 take 5 (step 'w' (step 'h' (foldr step [] ("y " ++ cycle "why "))))

下一个扩展是什么？ 您应该看到，为了对 step 进行模式匹配，您需要知道它是否为空列表。 为了找到答案，你必须对其进行评估，至少进行一点评估。 但第二项恰好是您要进行模式匹配的函数的 foldr 缩减。 换句话说，step 函数在不调用自身的情况下无法查看其参数，因此您有无限递归。

将其与第二个函数的扩展进行对比：

myWords_anotherReader (cycle "why ")
foldr step [""] (cycle "why ")
foldr step [""] ("why " ++ cycle "why ")
step 'w' (foldr step [""] ("hy " ++ cycle "why ")
let result = foldr step [""] ("hy " ++ cycle "why ") in
    ['w':(head result)] ++ tail result
let result = step 'h' (foldr step [""] ("y " ++ cycle "why ") in
    ['w':(head result)] ++ tail result

您可能会看到此扩展将继续，直到达到一个空间。 一旦到达一个空格，“head result”将获得一个值，并且您将产生答案的第一个元素。

我怀疑第二个函数对于不包含任何空格的无限字符串会溢出。 你能明白为什么吗？

Answer 3

第二个版本实际上不会评估结果，直到之后它开始生成自己的部分答案。 第一个版本通过模式匹配立即评估结果。

这些无限列表的关键是，在开始要求列表元素之前，您必须生成一些东西，以便输出始终“领先于”输入。

（我觉得这个解释不是很清楚，但这是我能做的最好的。）

Answer 4

库函数 foldr 具有以下实现（或类似实现）：

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f k (x:xs) = f x (foldr f k xs)
foldr _ k _ = k

myWords_FailsOnInfiniteList 的结果取决于 foldr 的结果，而 foldr 的结果又取决于 < code>step 取决于内部 foldr 的结果，而内部 foldr 取决于...等等无限列表，myWords_FailsOnInfiniteList 将用完无限量在产生第一个词之前先考虑空间和时间。

myWords_anotherReader 中的 step 函数在生成第一个单词的第一个字母之前不需要内部 foldr 的结果。 不幸的是，正如 Apocalisp 所说，它在生成下一个单词之前使用 O(第一个单词的长度) 空间，因为在生成第一个单词时，尾部 thunk 不断增长 tail ([...] ++ tail ([...] ++ tail (...)))。

---

相反，与

myWords :: String -> [String]
myWords = myWords' . dropWhile isSpace where
    myWords' [] = []
    myWords' string =
        let (part1, part2) = break isSpace string
        in part1 : myWords part2

使用可以定义为的库函数相比，

break :: (a -> Bool) -> [a] -> ([a], [a])
break p = span $ not . p

span :: (a -> Bool) -> [a] -> ([a], [a])
span p xs = (takeWhile p xs, dropWhile p xs)

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p (x:xs) | p x = x : takeWhile p xs
takeWhile _ _ = []

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p (x:xs) | p x = dropWhile p xs
dropWhile _ xs = xs

请注意，生成中间结果永远不会被未来的计算所阻碍，并且只需要 O(1) 空间，因为结果的每个元素都可供使用。

---

附录

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

myWords :: 字符串 ->   [细绳] 
  myWords 字符串=foldr 步骤[""] (dropWhile charIsSpace 字符串) 
     在哪里  
        步距 acc |   charIsSpace 空格 = "":acc 
        步骤 char (x:xs) = (char:x):xs 
        步骤_[]=错误“这应该是不可能的” 
  

（旁白：您可能不关心，但是库中的 words "" == []，但是您的 myWords "" = [""]。尾随的类似问题空格。）

看起来比 myWords_anotherReader 有很大改进，对于基于 foldr 的解决方案来说非常好。

\n -> tail $ myWords $ replicate n 'a' ++ " b"

不可能比 O(n) 时间做得更好，但 myWords_anotherReader 和 myWords 在这里都占用 O(n) 空间。 考虑到使用foldr，这可能是不可避免的。

更糟糕的是，

\n -> head $ head $ myWords $ replicate n 'a' ++ " b"

myWords_anotherReader 的复杂度为 O(1)，但新的 myWords 的复杂度为 O(n)，因为模式匹配 (x:xs) 需要进一步的复杂度。结果。

来解决此问题

myWords :: String -> [String]
myWords = foldr step [""] . dropWhile isSpace
   where 
      step space acc | isSpace space = "":acc
      step char ~(x:xs)              = (char:x):xs

您可以通过~ 引入“无可辩驳的模式” 。 无可辩驳的模式永远不会失败，也不会强制立即评估。