如何在递归F#函数中创建无重复元素的新列表？

好问题！咱们先拆解一下你的问题，分两部分来解决：一是if分支里能不能写多行代码，二是如何正确修复你的去重递归函数。

关于if分支的多行代码写法 #

首先，在F#的match表达式的if分支里完全可以写多行代码——你可以用大括号包裹代码块，或者利用F#的缩进语法（不需要大括号，只要保持代码缩进一致就行）。不过要注意：F#是表达式导向的语言，每个分支必须返回和函数类型匹配的值。

比如你要是想在else分支里先修改全局列表再构造返回值，写法可以是这样（但非常不推荐，原因后面说）：

let mutable newList = []  // 必须加mutable才能修改全局变量
let rec filtered inputList = 
    match inputList with 
    | [] -> [] 
    | h::t -> 
        if List.contains h newList then
            filtered t
        else
            newList <- h :: newList  // 先修改全局可变列表
            h :: (filtered t)

但这种依赖全局可变变量的写法有严重问题：你的函数会产生副作用，多次调用filtered会污染全局的newList，而且递归过程中newList的状态和你构造的返回列表可能不一致，很容易出现难以调试的bug。这违背了函数式编程的核心原则，也不是F#的惯用写法。

正确的递归去重实现 #

我们应该把「已经见过的元素」作为递归函数的参数传递进去，而不是依赖外部变量。这样每次递归调用时都带着当前的状态，函数变成纯函数（输入相同则输出相同，无副作用）。下面提供两种常用方案：

方案1：用列表跟踪已见过的元素（适合小列表） #

写一个内部辅助递归函数，接收两个参数：剩余待处理的输入列表，以及已经收集到的无重复元素列表。每次遇到新元素时，把它加入结果，并更新已见过的列表：

let removeDuplicates inputList =
    // 内部辅助递归函数：input是剩余待处理列表，seen是已见过的元素
    let rec filtered input seen =
        match input with
        | [] -> []
        | h::t ->
            if List.contains h seen then
                // 元素已存在，跳过，继续处理剩余列表
                filtered t seen
            else
                // 元素不存在，加入结果，同时把它加入seen传递给下一次递归
                h :: filtered t (h :: seen)
    // 初始调用：待处理列表是输入，已见过的元素为空
    filtered inputList []

方案2：用Set跟踪已见过的元素（效率更高，适合大列表） #

上面的方案中，List.contains是O(n)时间复杂度，当列表很大时效率很低。我们可以用F#的Set（基于平衡二叉树实现），它的contains操作是O(log n)，效率提升明显：

let removeDuplicates inputList =
    let rec filtered input seenSet =
        match input with
        | [] -> []
        | h::t ->
            if Set.contains h seenSet then
                filtered t seenSet
            else
                h :: filtered t (Set.add h seenSet)
    filtered inputList Set.empty

这两个方案都会保留原列表中元素第一次出现的顺序，而且都是纯函数，多次调用结果一致，没有副作用。

总结 #

你的原始代码问题核心是依赖全局变量跟踪状态，而递归函数的状态应该通过参数传递。虽然if分支可以写多行，但用可变全局变量的方式是坏实践——函数式编程更倾向于用无副作用的表达式来解决问题。

内容的提问来源于stack exchange，提问作者1010lll