Dlaczego ten rekurencyjny ogon nie jest?

Question

Pracuję nad książką Real-World Functional Programming i spróbowałem wymyślić własny przykład rekurencji ogona przed przeczytaniem przykładu książki (lista 10.2, s. 265). Przykład książki działa; moja powoduje przepełnienie stosu.

Znalazłem, jeśli użyję argumentu krotki lub wstępnie obliczyłem a + accum, a moje zadziała. Chcę zrozumieć, dlaczego.

let rnd = new System.Random() 
let test2 = List.init 1000000 (fun _ -> rnd.Next(-50, 51)) 

let rec sum2 list accum = 
    match list with 
    | [] -> accum 
    | a::b -> sum2 b a + accum 

let result = sum2 test2 0 

printfn "%d" result 

Answer 1

sum2 b a + accum 

pamiętać, że jest analizowany jako (sum2 b a) + accum, nie sum2 b (a + accum). To jest połączenie sum2 b a. Następnie bierze wynik tego połączenia i dodaje do niego accum. Ostatnim wyrażonym wyrażeniem jest więc dodanie, a nie wywołanie do sum2. Zatem wywołanie sum2 nie jest wywołaniem ogona.

Answer 2

Może kompilator czyta

a::b -> (sum2 b a) + accum 

zamiast

a::b -> sum2 b (a + accum)