La seguente funzione è ricorsiva in coda?

Ho una funzione in cui la linea a stella è una congiunzione che implica una chiamata ricorsiva. Poiché le congiunzioni funzionano, se h1 <> h2 la chiamata ricorsiva non verrà eseguita. Ma se la chiamata è fatta, allora il compilatore farà ancora marcia indietro ed eseguirà una serie di congiunzioni oltre i valori true? O eliminerà questo passaggio inutile?La seguente funzione è ricorsiva in coda?

In altre parole, la seguente funzione è efficacemente ricorsiva?

let isExtensionOf<'A when 'A : equality> (lst1 : list<'A>) (lst2 : list<'A>) : bool = 
    let rec helper (currLst1 : list<'A>) (currLst2 : list<'A>) : bool = 
     match currLst1, currLst2 with 
     | h1 :: _, [] -> false 
     | [], _ -> true 
     | h1 :: t1, h2 :: t2 -> (h1 = h2) && (helper t1 t2) // * 
    helper lst1 lst2

sì, lo so che la linea recitato dovrebbe essere scritto if h1 = h2 then helper t1 t2 else false. Ma sono solo curioso

Grazie in anticipo.

fonte

2016-07-01 Shredderroy

modo più semplice per rispondere a questo genere di domande: mangime in un elenco gigantesca, che si ritiene possano attivare il comportamento patologico e vedere cosa succede. –

Vorrei piuttosto compilarlo e quindi guardare il codice risultante con ILSpy. Più affidabile. Si noti inoltre che il risultato potrebbe differire a seconda che le ottimizzazioni siano abilitate. –

Beh, ha gestito liste di cardinalità '1.00.000.000' (cento milioni) senza battere ciglio, quindi supporrò che la mia domanda possa essere risolta in senso affermativo. – Shredderroy

Un altro semplice trucco per scoprire se la funzione è ricorsiva in coda è lanciare un'eccezione e osservare la traccia dello stack. Ad esempio, è possibile modificare helper come segue:

let rec helper (currLst1 : list<'A>) (currLst2 : list<'A>) : bool = 
    match currLst1, currLst2 with 
    | h1 :: _, [] -> failwith "!" 
    | [], _ -> failwith "!" 
    | h1 :: t1, h2 :: t2 -> (h1 = h2) && (helper t1 t2)

Se ora si chiama helper [1..10] [1..10], si ottiene una traccia dello stack che assomiglia a questo:

System.Exception:!
a FSI_0002.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:. Linea 4
a $ FSI_0003.main @() interrotta a causa di un errore

Ma se si modifica il codice in modo che non sia ricorsivo alla coda, ad es modificando l'ultima linea per effettuare la chiamata ricorsiva prima (helper t1 t2) && (h1 = h2), poi l'analisi dello stack mostra tutte le chiamate ricorsive:

System.Exception:! a FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: riga 4
a FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx : linea 4
a FSI_0004.helper [a] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: linea 4
a FSI_0004.helper [a] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: linea 4
a FSI_0004.helper [a] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: linea 4
a FSI_0004.helper [a] (FSharpList'1 currLst1, FSharpList '1 currLst2) in test.fsx: riga 4
a FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in te st.fsx: linea 4
a FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: linea 4
a FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList' 1 currLst2) in test.fsx: riga 4
a FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: riga 4
a FSI_0004.helper [A] (FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx: riga 4
a $ [email protected] Main()

fonte

2016-07-01 07:42:02

Se non mi manca qualcosa, questo metodo funzionerebbe solo in modalità Release. In modalità debug l'ottimizzazione della coda di coda è disabilitata (voglio dire generare chiamate tail taileckeckbox nelle proprietà). In modalità Debug questa casella è deselezionata per impostazione predefinita. – eternity

Da ILSpy sembrerebbe così:

IL_0000: nop 
    IL_0001: newobj instance void class '<StartupCode$ConsoleApplication3>.$Program'/[email protected]<!!A>::.ctor() 
    IL_0006: stloc.0 
    IL_0007: ldloc.0 
    IL_0008: ldarg.1 
    IL_0009: ldarg.2 
    IL_000a: tail. 
    IL_000c: call !!0 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!A>, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!A>>::InvokeFast<bool>(class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!0, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!1, !!0>>, !0, !1) 
    IL_0011: ret

fonte

2016-07-01 08:02:17 s952163

La seguente funzione è ricorsiva in coda?

risposta

Problemi correlati