12

我有两个 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 的重命名。

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

*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 []”开头的方程。将 step 函数的第二个参数与 [] 匹配是不可以的，因为它强制评估整个第二个参数（但需要在下面解释一个警告）。
  2. 有一次，我认为 (++) 可能会比 cons 更晚地评估它的右手参数，不知何故。所以，我想我可以通过将“= (char:x):xs”更改为“= [char:x] ++ xs”来解决这个问题。但那是不正确的。
  3. 在某一时刻，我认为将第二个 arg 与 (x:xs) 匹配的模式会导致该函数在无限列表中失败。我几乎是对的，但并不完全正确！正如我在上面的模式匹配中所做的那样，针对 (x:xs) 评估第二个 arg将导致一些递归。它会“转动曲柄”，直到碰到“：”（又名“缺点”）。如果这从未发生过，那么我的函数将无法针对无限列表成功。但是，在这种特殊情况下，一切正常，因为我的函数最终会遇到一个空格，此时会出现“cons”。并且通过匹配 (x:xs) 触发的评估将停在那里，避免无限递归。此时，“x”将被匹配，但 xs 仍将是一个 thunk，所以没有问题。（感谢 Ganesh 真正帮助我理解这一点）。
  4. 一般来说，您可以随意提及第二个 arg，只要您不强制评估它。如果你匹配了 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 时发生的第一件事是解释器检查第一个等式是否匹配。为此，它必须查看第二个参数是否为 []。为此，它必须评估第二个参数。

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

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

4

4 回答 4

7

尝试手动扩展表达式：

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

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

于 2009-05-12T04:52:31.300 回答
7

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

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

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

于 2009-05-12T05:05:11.030 回答
3

第二个版本直到开始产生自己的部分答案后才真正result进行评估。第一个版本通过对其进行模式匹配result 立即进行评估。

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

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

于 2009-05-12T04:14:20.193 回答
1

库函数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在产生它的第一个词之前会用完无限量的空间和时间.

在产生第一个单词的第一个字母之前，函数stepinmyWords_anotherReader不需要 inner 的结果。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

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

于 2009-05-12T15:35:43.653 回答