如何转换此函数以使用尾调用

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建议的那样,您应该使用模式匹配来提高可读性:

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#中,有一个使用序列表达式的尾递归方法,它沿着连续传递样式的行:

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

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