如何此功能轉換爲使用尾調用

Question

遞歸函數：

let rec listMerge (l1 : 'a list) (l2 : 'a list) = 
    if l1.IsEmpty then  l2 
    elif l2.IsEmpty then l1 
    else     l1.Head :: l2.Head :: listMerge l1.Tail l2.Tail 

現在，除非我很高興地看錯，這實際上並不執行尾調用，它只是看起來好像沒有，如果不是考慮到::是正確的聯想。

然後，我的印象（從我讀的東西，但現在找不到），這可以很容易地轉換爲尾部遞歸通過使用額外fun什麼的。

那麼，有可能嗎？碼？

我的回答：所以，這是我如何改變功能，這要歸功於以下答案：

let listMerge l1 l2 = 
    let rec mergeLoop (l1 : 'a list) (l2 : 'a list) acc = 
     if l1.IsEmpty then  (List.rev acc) @ l2 
     elif l2.IsEmpty then (List.rev acc) @ l1 
     else     mergeLoop l1.Tail l2.Tail (l2.Head :: l1.Head :: acc) 
    mergeLoop l1 l2 [] 

Answer 1

由於@Ramon建議，你應該使用pattern matching更好的可讀性：

let rec listMerge xs ys = 
    match xs, ys with 
    | [], _ -> ys 
    | _, [] -> xs 
    | x::xs', y::ys' -> x::y::listMerge xs' ys' 

正如你可以看到兩個缺點構造(::)上listMerge最後的操作，因此功能不tail-遞歸。

您可以使用蓄能器獲得一個尾遞歸的方式結果：

let listMerge xs ys = 
    let rec loop xs ys acc = 
     match xs, ys with 
     | [], zs | zs, [] -> (List.rev zs)@acc 
     | x::xs', y::ys' -> loop xs' ys' (y::x::acc) 
    List.rev (loop xs ys []) 

在上面的功能，如果你添加一些圖案的第一List.rev呼叫可以避免解構兩個列表，直到他們都是空的。

在F＃中，存在使用sequence expressions尾遞歸方法是沿continuation-passing style線：

let listMerge xs ys = 
    let rec loop xs ys = 
     seq { 
      match xs, ys with 
      | [], zs | zs, [] -> yield! zs 
      | x::xs', y::ys' -> 
       yield x 
       yield y 
       yield! loop xs' ys' 
     } 
    loop xs ys |> Seq.toList 

我喜歡這種方法，因爲它很方便，靠近你的原始配方。使用蓄電池

Answer 2

可以積累在後續調用listMerge構建的結果，最後返回累加結果。我的F＃技能相當生鏽，但這裏有一個簡單的Lisp函數。

(defun list-merge (xs ys &optional acc) 
    (cond ((< 0 (length xs)) (list-merge (rest xs) ys (cons (first xs) acc))) 
     ((< 0 (length ys)) (list-merge xs (rest ys) (cons (first ys) acc))) 
     (t acc))) 

(list-merge '(1 2 3) '(3 4 5)) ;=> (5 4 3 3 2 1) 
(list-merge '() '(1 2))  ;=> (2 1) 
(list-merge '() '())   ;=> nil 

Answer 3

簡易版：

let rec listMerge (l1 : 'a list) (l2 : 'a list) acc = 
    if l1.IsEmpty then  (List.rev l2)@acc 
    elif l2.IsEmpty then (List.rev l1)@acc 
    else     listMerge l1.Tail l2.Tail (l1.Head :: l2.Head :: acc) 

我備有二萬餘元列表測試這一點，並沒有堆棧溢出，所以我有理由相信這是尾遞歸。

Answer 4

我想你必須重用F# PowerPack中找到的原始F＃代碼。
其實，你需要的是List.fold2，除了功能不應該拋出一個異常SR.listsHadDifferentLengths的情況下，如果列表大小是不同的，而是處理的時間越長列表的其餘部分，像這樣：

let l1 = ["A1"; "A2"; "A3"; "A4"; "A5"; "A6"; "A7"] 
let l2 = ["B1"; "B2"; "B3"; "B4"] 

let expectedResult = ["A1"; "B1"; "A2"; "B2"; "A3"; "B3"; "A4"; "B4"; "A5"; "A6"; "A7"] 

這裏的我們如何做到這一點：

[<CompiledName("Fold2Tail")>] 
let fold2Tail<'T1,'T2,'State> f g1 g2 (acc:'State) (list1:list<'T1>) (list2:list<'T2>) = 
    let f = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f) 
    let g1 = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(g1) 
    let g2 = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(g2) 
    let rec loop acc list1 list2 = 
     match list1, list2 with 
     | [], [] -> acc 
     | _, [] -> g1.Invoke(acc, list1) 
     | [], _ -> g2.Invoke(acc, list2) 
     | (h1::t1),(h2::t2) -> loop (f.Invoke(acc,h1,h2)) t1 t2 
    loop acc list1 list2 

g1和g2是'State -> 'T1 list -> 'State型和'State -> 'T2 list -> 'State的謂詞，相應地。他們告訴如何處理這兩個列表的剩餘部分。注意其中有兩個，因爲一般情況下，'T1和'T2是不同的類型。是的，它有些開銷，但您可以輕鬆地將其降低到您的需求，從而犧牲普遍性。

用法：

let ret = 
    fold2Tail 
     (fun s x y -> [ yield! s; yield x; yield y ]) // f 
     List.append // g1 
     List.append // g2 
     []   // 'State 
     l1 l2 

Answer 5

你應該使用模式匹配：

let rec merge xs ys = 
    match xs, ys with 
    | [], xs | xs, [] -> xs 
    | x::xs, y::ys -> x::y::merge xs ys 

要獲得尾調用，您可以使用累加器：

let merge xs ys = 
    let rec loop xys xs ys = 
    match xs, ys with 
    | [], xs | xs, [] -> List.fold (fun xs x -> x::xs) xs xys 
    | x::xs, y::ys -> loop (y::x::xys) xs ys 
    loop [] xs ys 

或繼續傳遞風格：

let merge xs ys = 
    let rec loop xs ys k = 
    match xs, ys with 
    | [], xs | xs, [] -> k xs 
    | x::xs, y::ys -> loop xs ys (fun xys -> k(x::y::xys)) 
    loop xs ys id