如何使用尾遞歸

我只是尋找一個小小的建議重寫代碼，如何使用尾遞歸如何使用尾遞歸

open Core.Std;; 

let rec dig x = 
    match x with 
    | 0 -> [] 
    | _ -> x :: dig (x - 1) 
;; 


let() = 
    let numbers = dig 10 in 
    List.iter ~f:(Printf.printf "%d, ") numbers; 
    Printf.printf "\n"; 
;;

重寫代碼的任何建議，將有助於

來源

2015-09-15 grigoriytretyakov

let dig x = 
    let rec f x s = 
     match x with 
     | 0 -> s 
     | _ -> f (x-1) (x::s) 
    f x []

這是你想要的嗎？它使用尾遞歸。

編輯：對於seq遞減，只需將（x :: s）替換爲（List.append s [x]）或（s @ [x]），但這不是一個好主意，List.rev是好：

let dig x = 
    let rec f x s = 
     match x with 
     | 0 -> s 
     | _ -> f (x-1) (s @ [x]) 
    f x []

來源

2015-09-15 15:52:08 Syeerzy

這不完全是我要找的。您的功能會增加順序，但我正在嘗試創建遞減順序。 – grigoriytretyakov

你應該用'List.rev'來取消結果以保持順序 – ivg

let dig x = 
    let rec f s z = 
    if z = x then s 
    else f (z::s) (z+1) 
    in 
    f [] 0

不知道這是否你的船浮筒：您可能需要調整取決於邊界的情況下，如果你想爲0或包含起始編號。

來源

2015-09-15 19:18:07 lambdapower

好了，它似乎可以有多種解決方案

open Core.Std;; 


let rec digtail ?(l=[]) x = 
    match x with 
    | 0 -> l 
    | _ -> digtail ~l: (l @ [x]) (x - 1) 
;; 


let() = 
    let numbers = digtail 10 in 
    List.iter ~f:(Printf.printf "%d, ") numbers; 
    Printf.printf "\n"; 
;;

感謝所有，你幫了不少忙。

來源

2015-09-16 09:52:11 grigoriytretyakov

'l @ [x]'使得你的函數是二次的而不是線性的：對於每次調用，你遍歷到目前爲止建立的整個'l'一個單一的元素。另外'@'本身並不是尾遞歸，因此實際上你將問題從'digtail'轉換爲'@'。你真的應該更喜歡Syeerzi的解決方案（最後一個'List.rev'由ivg提出） – Virgile

如果你不想向後建築名單（這在我看來是完全沒有問題），也不符合0而不是n開始你的遞歸後使用List.rev，你可以使用某種延續：

let dig2 x = 
    let rec aux x kont = 
    match x with 
    | 0 -> kont 
    | _ -> aux (x-1) (fun l -> kont (x::l)) 
in 
aux x (fun l -> l) [];;

基本上每個步驟都會返回一個函數，給定由其餘步驟構建的列表，它將爲其添加x。我們用身份函數開始遞歸，因爲我們還沒有任何東西需要構建。然後，當我們退出遞歸時，我們只需要將空列表應用到獲得的函數中。

來源

2015-09-16 13:50:54 Virgile

你知道，這不是我不喜歡使用List.rev或內部遞歸函數的解決方案，我只是想找到解決這個問題的更多方法簡單的任務。我只開始學習OCaml，並希望看到其他人如何在簡單任務中使用它。（關於我的英語學習，我可以說同樣的話）。 – grigoriytretyakov

這對我很好。我只是想強調，前兩個答案比我更習慣，這確實只是爲了完整。 – Virgile

「你可以使用某種延續」也稱爲「差異列表」。 – gallais

如何使用尾遞歸

回答

相關問題