recursion - 创建序列序列导致 StackOverflowException

Question

我正在尝试将一个大文件拆分成许多小文件。每个拆分发生的位置基于检查每个给定行的内容返回的谓词(isNextObject 函数)。

我试图通过 File.ReadLines 函数读取大文件，这样我就可以一次一行地遍历文件，而不必将整个文件保存在内存中。我的方法是将序列分组为一系列较小的子序列(每个要写出的文件一个)。

我发现了 Tomas Petricek 在 fssnip 上创建的一个名为 groupWhen 的有用函数.此函数非常适合我对文件的一小部分进行的初始测试，但在使用真实文件时会抛出 StackoverflowException。我不确定如何调整 groupWhen 函数来防止这种情况发生(我仍然是 F# 菜鸟)。

这是代码的简化版本，仅显示将重新创建 StackoverflowExcpetion::的相关部分

// This is the function created by Tomas Petricek where the StackoverflowExcpetion is occuring
module Seq =
  /// Iterates over elements of the input sequence and groups adjacent elements.
  /// A new group is started when the specified predicate holds about the element
  /// of the sequence (and at the beginning of the iteration).
  ///
  /// For example: 
  ///    Seq.groupWhen isOdd [3;3;2;4;1;2] = seq [[3]; [3; 2; 4]; [1; 2]]
  let groupWhen f (input:seq<_>) = seq {
    use en = input.GetEnumerator()
    let running = ref true

    // Generate a group starting with the current element. Stops generating
    // when it founds element such that 'f en.Current' is 'true'
    let rec group() = 
      [ yield en.Current
        if en.MoveNext() then
          if not (f en.Current) then yield! group() // *** Exception occurs here ***
        else running := false ]

    if en.MoveNext() then
      // While there are still elements, start a new group
      while running.Value do
        yield group() |> Seq.ofList } 

这是使用 Tomas 函数的代码要点:

module Extractor =

    open System
    open System.IO
    open Microsoft.FSharp.Reflection

    // ... elided a few functions include "isNextObject" which is
    //     a string -> bool (examines the line and returns true
    //     if the string meets the criteria to that we are at the 
    //     start of the next inner file)

    let writeFile outputDir file =
        // ... write out "file" to the file system
        // NOTE: file is a seq<string>

    let writeFiles outputDir (files : seq<seq<_>>) =
        files
        |> Seq.iter (fun file -> writeFile outputDir file)

下面是控制台应用程序中使用这些函数的相关代码:

let lines = inputFile |> File.ReadLines

writeFiles outputDir (lines |> Seq.groupWhen isNextObject)

关于阻止 groupWhen 炸毁堆栈的正确方法有什么想法吗？我不确定如何将函数转换为使用累加器(或改为使用延续，我认为这是正确的术语)。

Answer 1

这样做的问题是group()函数返回一个列表，这是一个急切求值的数据结构，这意味着每次调用group()它必须运行到最后，将所有结果收集到一个列表中，然后返回列表。这意味着递归调用发生在同一评估中 - 即真正递归地 - 从而产生堆栈压力。

为了缓解这个问题，你可以用惰性序列替换列表:

let rec group() = seq {
   yield en.Current
   if en.MoveNext() then
     if not (f en.Current) then yield! group()
   else running := false }

但是，我会考虑不太激进的方法。这个例子很好地说明了为什么你应该避免自己进行递归，而应该求助于现成的折叠。

例如，从您的描述来看，Seq.windowed 似乎适合您。