Можно ли вызвать оптимизацию групповой функции в 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 я в растерянности. Я действительно надеюсь сделать эту работу с общими последовательностями ..

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

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 (что будет зависеть от количества элементов, обработанных до возникновения исключения).