È possibile tail chiamata ottimizzare una funzione di raggruppamento in F # usando sequenze?

Question

Ecco il mio tentativo che non è una chiamata di coda ottimizzata perché ho bisogno di smaltire l'enumeratore:

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

.

Ed qui è l'uso di esempio:

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

.

Se posso evitare di usare l'enumeratore (I.e. Seq.head AND Seq.tail) Potrei farlo funzionare ma senza Seq.tail sono in perdita.Spero davvero di fare questo lavoro con sequenze generiche ..

E FYI So che questo codice non funzionerà nel suo stato attuale perché finirei per aver smesso di smaltire l'enumeratore più volte.

Answer 1

È possibile spostare il blocco try .. finally dalla funzione some interni (dove viene inserito durante ogni iterazione) alla funzione principale.Quindi la funzione ricorsiva interiore some diventa corsivo-ricorsivo:

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() }

.

o ancora meglio, è possibile implementare la sequenza che viene restituita da Group utilizzando il costrutto use:

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

.

In realtà, penso che questo sia più corretto del tuo codice originale, perché chiama il metodo Dispose solo una volta.Nella tua versione, verrebbe chiamato una volta per ogni volta che l'esecuzione entra in generazione some (che dipenderebbe dal numero di elementi elaborati prima che accada un'eccezione).