为什么第一个Haskell函数FAIL处理无限列表,而第二个片段SUCCEEDS带有无限列表？

Question

我有两个Haskell函数,这两个函数看起来和我非常相似.但是第一个FAILS反对无限列表,第二个反对无限列表成功.我一直在努力确定原因,但无济于事.

两个片段都是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 []"开头的2个方程式.将步骤函数的第二个参数与[]匹配是一个禁忌,因为它强制对整个第二个arg进行求值(但需要注意下面的解释).
2. 有一次,我曾经想过(++)可能会稍后评估它的右手论证,而不是以某种方式.所以,我想我可以通过将"=(char:x):xs"更改为"= [char:x] ++ xs"来解决问题.但这是不正确的.
3. 有一次,我认为将第二个arg与(x:xs)匹配的模式会导致函数对无限列表失败.我几乎是对的,但并不完全!评估针对(X:XS)第二精氨酸,如我在模式匹配做以上,WILL引起一些递归.它将"转动曲柄"直到它击中":"(又名"cons").如果这种情况从未发生过,那么我的函数就无法在无限列表中成功.但是,在这种特殊情况下,一切都很好,因为我的函数最终会遇到一个空格,此时会出现"缺点".通过匹配(x:xs)触发的评估将在那里停止,避免无限递归.此时,"x"将匹配,但xs仍然是一个thunk,所以没有问题.(感谢Ganesh帮我理解这一点).
4. 一般来说,你可以提到所有你想要的第二个arg,只要你不强制评估它.如果你匹配x:xs,那么只要你不强制评估它就可以提到你想要的xs.

所以,这是修改后的代码.我通常试图避免头部和尾部,仅仅因为它们是部分功能,而且因为我需要练习编写相应的模式匹配.

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 _ []"等式时,一切都很好!无限列表仍然没有问题!.为什么？

因为修正后的代码中的第3个等式永远不会达到!

实际上,请考虑以下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时发生的第一件事是解释器检查方程式1是否匹配.为此,必须查看第二个arg是否为[].要做到这一点,它必须评估第二个arg.

将等式向下移动低于其他等式确保从不尝试第三个等式,因为第一个或第二个模式总是匹配.第三个等式仅仅是为了省去非详尽模式警告.

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

Answer 1

尝试手动扩展表达式:

 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

您可能会看到此扩展将持续到达到空间.一旦达到空格,"头部结果"将获得一个值,您将产生答案的第一个元素.

我怀疑第二个函数将溢出无限字符串,不包含任何空格.你能明白为什么吗？

Answer 2

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

它不必以这种方式编写,但是你的第二个版本有点难看,因为它依赖于具有特定格式的步骤的初始参数,并且很难看出头/尾永远不会出错.(我甚至不能100%肯定他们不会!)

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