Можно ли использовать функцию tail для оптимизации функции группировки в f # с использованием последовательностей?

Question

Вот моя попытка, которая не является хвост вызов оптимизирован, потому что мне нужно утилизировать перечислителем:

let Group func seed (items : seq<'t>) = 
    let rec some (i : IEnumerator<'t>) state = seq { 
     try 
      if i.MoveNext() 
      then 
       let newstate, iscomplete = func (i.Current) state 
       if iscomplete 
       then 
        yield newstate 
        yield! some i newstate 
      else 
       yield state 
     finally 
      i.Dispose() } 

    some (items.GetEnumerator()) seed 

А вот пример использования:

let buffer maxBufferSize items = 
    Group (fun item state -> 
     let newstate = [ item ] |> List.append state 
     if newstate.Length >= maxBufferSize 
     then (newstate, true) 
     else (newstate, false)) List.empty items 

Если я могу избежать использования нумератор (т.е. Seq.head AND Seq.tail) Я мог бы заставить его работать, но без Seq.tail Я в затруднении. Я действительно надеюсь сделать эту работу с родовыми последовательностями.

И FYI Я знаю, что этот код не будет работать в текущем состоянии, потому что я в конечном итоге удалю перечислитель несколько раз.

Answer 1

Вы можете переместить блок try .. finally из внутренней функции some (где он вводится на каждой итерации) в основную функцию. Тогда внутренняя рекурсивная функция some становится хвостовой рекурсией:

let Group func seed (items : seq<'t>) = 
    // The handling of exceptions is done by the caller, 
    // so 'some' does not need to handle exceptions... 
    let rec some (i : IEnumerator<'t>) state = seq { 
     if i.MoveNext() 
     then 
      let newstate, iscomplete = func (i.Current) state 
      if iscomplete then 
       yield newstate 
       // Recursive call in tail-call position 
       yield! some i newstate 
     else 
      yield state } 

    // Return a sequence that wraps the obtains the IEnumerator 
    // and guarantees that it gets disposed if 'some' fails 
    seq { 
     let i = items.GetEnumerator() 
     try 
      // This is still not-tail recursive 
      yield! some i seed 
     finally 
      i.Dispose() } 

Или еще лучше, вы можете реализовать последовательность, которая возвращается из Group используя use конструкцию:

seq { 
     use i = items.GetEnumerator() 
     // This is still not-tail recursive 
     yield! some i seed } 

На самом деле, я думаю, что это более корректным, чем ваш исходный код, потому что он вызывает метод Dispose только один раз. В вашей версии он будет вызываться один раз для каждого запуска выполнения в some (который будет зависеть от количества обработанных элементов до возникновения исключения).