时间戳

首页 > 解决方案 > F# - 在排序列表中插入元素（尾递归）

f# - F# - 在排序列表中插入元素（尾递归）

问题描述

我正在尝试将以下正常递归代码转换为 F# 中的尾递归，但我失败得很惨。

let rec insert elem lst = 
    match lst with
    | [] -> [elem]
    | hd::tl -> if hd > elem then 
                    elem::lst
                else 
                    hd::(insert elem tl) 

let lst1 = []

let lst2 = [1;2;3;5]

printfn "\nInserting 4 in an empty list:  %A" (insert 4 lst1)
printfn "\nInserting 4 in a sorted list:  %A" (insert 4 lst2)

你们能帮忙吗？不幸的是，我是 f# 的初学者。另外，谁能指出我理解尾递归的好教程？

标签： f#tail-recursion

解决方案

尾递归的要点如下：从函数返回之前的最后一个操作是对自身的调用；这被称为尾调用，并且是尾递归得名的地方（递归调用在最后，即尾位置）。

您的函数不是尾递归的，因为它的至少一个分支在递归调用（list cons 运算符）之后有一个操作。

将递归函数转换为尾递归函数的常用方法是添加一个参数来累积中间结果（累加器）。当涉及到列表时，当您意识到唯一的基本列表操作是添加一个元素时，这也意味着在您处理完列表后，它将被反转，因此结果累加器通常必须反转再次。

考虑到所有这些要点，并且考虑到我们不想通过添加从调用者的角度来看多余的参数来更改函数的公共接口，我们将实际工作移至内部子函数。这个特定的函数稍微复杂一些，因为在插入元素之后，除了再次连接两个部分列表之外别无他法，其中一个现在是相反的顺序，而另一个不是。我们创建了第二个内部函数来处理该部分，因此整个函数如下所示：

let insert elm lst =
    let rec iter acc = function
        | [] -> List.rev (elm :: acc)
        | (h :: t) as ls ->
            if h > elm then finish (elm :: ls) acc
            else iter (h :: acc) t
    and finish acc = function
        | [] -> acc
        | h :: t -> finish (h :: acc) t
    iter [] lst

为了进一步学习，Scott Wlaschin 的F# for Fun and Profit是一个很好的资源，尾递归在关于递归类型等的更大章节中处理：https ://fsharpforfunandprofit.com/posts/recursive-types-and-folds

推荐阅读