這是F＃函數尾遞歸，其中遞歸函數在函數內多次調用？

有幾個關於尾遞歸函數的問題，例如this和this，但找不到與以下內容類似的內容。這是F＃函數尾遞歸，其中遞歸函數在函數內多次調用？

我的理解是，tail-call優化函數應該在上次調用中返回一個累加值，而無需進一步評估。使用階乘函數很容易理解，例如，對循環進行了優化2。但在其他情況下，例如在下面，最後一次電話是什麼？有很多這樣的函數在函數體內被遞歸調用多次。

布賴恩建議找出一種方式，但我不知道如何使它尾調優化。我可以將--tailcalls標誌傳遞給編譯器自動執行，但它總是成功嗎？

f和g返回相同的類型。

任何幫助尾調優化上述代碼將不勝感激。

來源

2012-05-28 vis

正如Jon所說，你的函數不是尾遞歸的。基本問題是它需要多次調用多次（xs列表中的每個元素一次，這是在傳遞給List.map的lambda函數中完成的）。

如果實際需要進行多次遞歸調用，則使用延續傳球風格或命令式堆疊可能是唯一的選擇。延續背後的想法是，每個函數都會接受另一個函數（作爲最後一個參數），當結果可用時應該執行該函數。

下面的例子顯示了基於普通版（左）和繼續（右側）

let res = foo a b       fooCont a b (fun res -> 
printfn "Result: %d" res      printfn "Result: %d" res)

需要編寫一個延續傳遞風格的功能，你需要使用一個基於延續fold功能。你可以先避免通過移動map完成的操作成fold lambda函數使用map：

List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs)

變爲：

List.fold (fun state xxs -> g state (myfunc f xxs)) acc xs

然後你可以重寫代碼如下所示（請注意這兩個f和g你沒有在你的問題中顯示現在是基於延續的函數，所以他們採取額外的參數，這代表了延續）：

// The additional parameter 'cont' is the continuation to be called 
// when the final result of myfunc is computed 
let rec myfunc' f (T (x,xs)) cont = 
    if (List.isEmpty xs) then 
    // Call the 'f' function to process the last element and give it the 
    // current continuation (it will be called when 'f' calculates the result) 
    f x cont 
    else 
    // Using the continuation-based version of fold - the lambda now takes current 
    // element 'xxs', the accumulated state and a continuation to call 
    // when it finishes calculating 
    List.foldCont (fun xxs state cont -> 
     // Call 'myfunc' recursively - note, this is tail-call position now! 
     myfunc' f xxs (fun res -> 
     // In the continuation, we perform the aggregation using 'g' 
     // and the result is reported to the continuation that resumes 
     // folding the remaining elements of the list. 
     g state res cont)) acc xs cont

的List.foldCont功能是fold基於延續的版本，可以按如下方式寫入：

module List = 
    let rec foldCont f (state:'TState) (list:'T list) cont = 
    match list with 
    | [] -> cont state 
    | x::xs -> foldCont f state xs (fun state -> 
     f x state cont)

既然你沒有張貼一個完整的工作示例，我真的無法測試的代碼，但我認爲它應該工作。

來源

2012-05-29 00:00:43

難道你不需要'mapCont'或缺點在你的答案嗎？ –

我花了一段時間來做一些關於延續傳遞風格的背景閱讀，並最終能夠實現我的代碼中的更改。但是，我還發現我可以更改我的代碼（在上面的問題中真正修剪了這些代碼），以便不會多次調用正文中的遞歸函數。但這裏提供的答案確實有幫助。需要使用這種風格。 – vis

我的理解是，尾部調用優化功能應在其最後一次調用返回的累計值...

差不多。當遞歸調用全部出現在尾部位置時，尾遞歸是。尾部位置意味着調用者直接從其被調用者返回結果。

在下面，最後的呼叫是什麼？

在尾部位置有兩個呼叫。首先，致電f。其次，致電List.fold。遞歸調用不在尾部位置，因爲它的返回值不是由調用者直接返回的。

if (List.isEmpty xs) then f x

此外，使用模式的匹配，而不是isEmpty和朋友。

任何幫助尾調優化上述代碼將不勝感激。

您必須在任何人能夠幫助您編寫尾遞歸版本之前發佈工作代碼或至少一個規範。一般來說，最簡單的解決方案是以延續傳球風格或命令式風格寫作。

來源

2012-05-28 22:55:19

這是F＃函數尾遞歸，其中遞歸函數在函數內多次調用？

回答

相關問題