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