尾递归breakAt
标准累加器引入技巧将产生如下所示的结果：
breakAt :: Char -> String -> (String, String)
breakAt needle = breakAtAcc []
where breakAtAcc :: String -> String -> (String, String)
breakAtAcc seen [] = (reverse seen, [])
breakAtAcc seen cs@(c:cs')
| c == needle
= (reverse seen, cs)
| otherwise
= breakAtAcc (c : seen) cs'
这个的递归部分is尾递归，尽管我们以错误的顺序处理组成返回值的预分割部分的字符来构建列表，所以最后需要将它们颠倒过来。然而，即使忽略这一点（使用没有reverse），这可能更糟。
在 Haskell 中，如果您担心在许多其他语言的深度递归中看到的堆栈溢出错误，那么您担心的是错误的事情（通常通过尾调用优化来阻止，因此尾递归是可取的）。 Haskell 没有这种堆栈溢出。哈斯克尔确实有a堆栈，它可能会溢出，但它不是命令式语言的正常调用堆栈。
例如，如果我启动 GHCighci +RTS -K65k显式地将最大堆栈大小设置为 65 KB（大约是我可以让它启动的最小值），然后触发标准foldr (+)堆栈溢出并不需要太多：
λ foldr (+) 0 [1..3000]
*** Exception: stack overflow
仅仅 3,000 个递归步骤就可以杀死它。但我可以运行你的br on much更大的列表没有问题：
λ let (pre, post) = br 'b' (replicate 100000000 'a' ++ "b") in (length pre, length post)
(100000000,1)
it :: (Int, Int)
这是 1 亿个非尾递归步骤。如果它们中的每一个都占用一个堆栈帧并且它们适合 65 KB 堆栈，那么每个字节我们将获得大约 1500 个堆栈帧。显然，这种递归实际上并不会导致其他语言中那样的堆栈消耗问题！那是因为它是not导致堆栈溢出的递归深度本身foldr (+) 0 [1..3000]。 （如果你想知道什么，请参阅最后一节does造成它）
优势br有一个尾递归版本，例如breakAt是它是富有成效的。如果您只对第一个感兴趣n前缀的字符，那么最多n将检查输入字符串的字符（如果您对分割后的字符串感兴趣，那么显然需要检查足够的字符串才能找到分割）。您可以通过运行来观察这一点br and breakAt在长输入字符串上并采用少量前缀，如下所示：
λ let (pre, post) = br 'b' (replicate 100000000 'a' ++ "b") in take 5 pre
"aaaaa"
it :: [Char]
如果你尝试同样的事情breakAt（即使您拨打电话reverse），它首先只会打印"然后花很长时间思考，最后才想出剩下的"aaaaa"。那是因为它在返回之前必须找到分割点anything除了另一个递归调用；在到达分割点之前，前缀的第一个字符不可用。这就是essence尾递归；没有办法修复它。
您可以通过使用更明确地看到它undefined:
λ let (pre, post) = br 'b' ("12345" ++ undefined) in take 5 pre
"12345"
it :: [Char]
λ let (pre, post) = breakAtRev 'b' ("12345" ++ undefined) in take 5 pre
"*** Exception: Prelude.undefined
CallStack (from HasCallStack):
error, called at libraries/base/GHC/Err.hs:74:14 in base:GHC.Err
undefined, called at <interactive>:18:46 in interactive:Ghci8
br可以返回前 5 个字符，而不检查是否有第 6 个字符。breakAt（有还是没有reverse）强制更多的输入，因此命中undefined.
这是 Haskell 中的常见模式。更改算法以使其尾递归频繁地提高性能worse。如果最终返回值是像这样的小类型，那么您确实需要尾递归Int, Double等不能以“渐进”方式消耗的；但您需要确保您使用的任何累加器参数是strictly在这种情况下评估！这就是为什么要总结一个列表foldl'比foldr;没有办法“逐渐”消耗总和，所以我们想要尾递归foldl，但它必须是strict变体foldl'或者即使它是尾递归我们仍然会遇到堆栈溢出！但是，当您返回列表或树之类的内容时，如果您可以安排逐渐消耗结果以使输入逐渐被读取，那就更好了。尾递归从根本上不允许这样做。
Haskell 中堆栈消耗的原因是什么？
哈斯克尔很懒。因此，当您调用递归函数时，它不一定会像严格语言中那样立即一直运行到递归的“底部”（要求递归每个级别的堆栈帧立即“活动”） ，如果它们不能通过诸如尾部调用消除之类的方法来优化）。当然，它根本不需要运行，只有在需要结果时才运行，但即便如此，“需求”也会导致函数只运行到“弱头范式”。它有一个奇特的技术定义，但它或多或少意味着该函数将运行直到它产生一个数据构造器.
因此，如果函数的代码本身返回一个数据构造函数，如br确实（它的所有情况都返回对构造函数(,)），然后输入该函数将在该单个步骤结束时完成。数据构造函数的字段可能包含用于进一步递归调用的 thunk（就像它们在br），但只有当某些模式在此构造函数上匹配以提取这些字段，然后对它们进行模式匹配时，这些递归调用才会实际运行。通常这只是about发生这种情况，因为返回的构造函数上的模式匹配首先导致了运行此函数的需求，但它仍然得到解决after该函数返回。因此，当第一个调用“仍在运行”时，不必在构造函数字段中进行任何递归调用，因此当我们输入递归调用时，我们不必为其保留调用堆栈帧。 （我确信实际的 GHC 实现做了很多我没有介绍的奇特技巧，所以这张图可能在细节上不正确，但它对于语言如何“工作”来说是一个足够准确的心理模型）
但是如果函数的代码doesn't直接返回数据构造函数？如果它返回怎么办另一个函数调用？函数调用在需要返回值之前不会运行，但我们正在考虑的函数仅运行是因为its要求返回值。这意味着它返回的函数调用是also要求，所以我们必须输入它。
我们可以使用尾部调用消除来避免为此需要调用堆栈帧。但是如果代码为this函数进行模式匹配（或使用seq，或者严格分析决定要求尽早提出论点，等等）？如果它匹配的东西已经被评估为数据构造函数，那么没关系，它现在可以运行模式匹配。但如果匹配的东西本身就是一个 thunk，这意味着我们必须输入一些随机的其他函数并运行它足够远以生成其最外层的数据构造函数。Now我们需要一个堆栈帧来记住当其他函数完成时要返回到哪里。
因此，Haskell 中的堆栈消耗不是直接来自调用深度，而是来自“模式匹配深度”或“需求深度”；我们必须在找不到最外层数据构造函数的情况下输入 thunk 的深度。
So br is 完全没问题对于这种堆栈消耗；它的所有分支立即返回一对构造函数(,)。递归情况需要再次调用br在其字段中，但正如我们所见，这不会导致堆栈增长。
如果是breakAt（更确切地说breakAtAcc），递归情况下的返回值是我们必须输入的另一个函数调用。在一路运行到分割点之后，我们只能到达一个可以停止的点（数据构造函数）。所以我们失去了懒惰和生产力，但仍然不会因为尾调用消除而导致堆栈溢出。
问题在于foldr (+) 0 [1..3000]是否返回0 + <thunk>。这不是一个数据构造函数，它是一个函数调用+，所以必须输入。但+两个参数都是严格的，所以before它返回它将在 thunk 上进行模式匹配，要求我们运行它（从而添加一个堆栈帧）。那 thunk 将评估foldr (+) 1 [2..3000] to 1 + <thunk>，并输入+再次将迫使that重击2 + thunk等等，最终耗尽堆栈。但调用深度为foldr从技术上讲没有什么害处，而是嵌套的+很高兴foldr生成消耗堆栈的内容。如果您可以按字面意思编写一个类似的巨大加法链（并且 GHC 会天真地评估它而无需重写任何内容），那么在根本没有调用深度的情况下也会发生相同的堆栈溢出。如果你使用foldr使用不同的函数，您可以将无限列表处理到无限深度，而根本不消耗堆栈。
TLDR
你可以有一个尾递归break，但比中的版本更糟糕base。深度递归是一个问题strict使用调用堆栈的语言，但 Haskell 不使用。深的模式匹配是类似的问题，但需要的不仅仅是计算递归深度来发现这一点。因此，尝试使 Haskell 中的所有递归都是尾递归通常会使您的代码变得更糟。
