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

StackOverflow https://stackoverflow.com/questions/851078

题

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

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

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

有帮助吗？

解决方案

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

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

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

其他提示

尝试手动扩展表达式：

 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”将获得一个值，并且您将产生答案的第一个元素。

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

第二个版本实际上并没有评估 result 直到 后 它已经开始给出自己的部分答案。第一个版本评估 result 立即地 通过对其进行模式匹配。

这些无限列表的关键是你必须生成 某物 在开始要求列表元素之前，以便输出始终“保持在输入之前”。

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

库函数 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 这取决于结果 step 这取决于内部的结果 foldr 这取决于...等等无限列表， myWords_FailsOnInfiniteList 在产生第一个单词之前会占用无限的空间和时间。

这 step 函数于 myWords_anotherReader 不需要内部结果 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 :: 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"

（在旁边：你可能不在乎，但 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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top