function - 如何将此函数转换为使用尾调用

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'

如您所见，两个 cons 构造函数 (::)是 listMerge 上的最后操作所以该函数不是尾递归的。

您可以使用累加器以尾递归方式获取结果:

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

我喜欢这种方法，因为它方便且接近您的原始配方。