F# 删除列表中第一次出现的元素

Question

我想删除列表中给定元素第一次出现的可能重复项。例如，带有 [1; 6; 1].我只想删除 1 一次并 returns 列表 [6;1]。我当前的实现：

let rec remove l x =
        match l with
        | [] -> []
        | h::t when h = x -> t
        | h::t -> h::(remove l h)

这仅适用于我要删除的数字是第一个元素的列表。对于像 [6; 7; 6] 如果我想删除数字 7 和 return [6; 6].它不会遍历列表并使用我当前的实现删除 7。如何遍历整个列表并仅删除第一次出现的元素？

Answer 1

我最终编写了与您相同的代码，而且它似乎工作得很好。我重新排序了参数以获得更好的管道。我也可以努力制作这个 tail-recursive.

let rec removeFirst elem xs =
    match xs with
    | [] -> []
    | h :: t when elem = h -> t
    | h :: t -> h :: (removeFirst elem t)

> removeFirst 2 [1;2;2;1];;
val it: int list = [1; 2; 1]

Answer 2

Tail-call优化版

let removeFirst elem list =
    let rec loop head tail =
        match tail with
        | [] -> list
        | x :: xs when x = elem -> (List.rev head) @ xs
        | x :: xs -> loop (x::head) xs
    loop [] list

removeFirst 1 [1; 2; 3] |> printfn "%A" // [2; 3]
removeFirst 2 [1; 2; 3] |> printfn "%A" // [1; 3]
removeFirst 3 [1; 2; 3] |> printfn "%A" // [1; 2]
removeFirst 4 [1; 2; 3] |> printfn "%A" // [1; 2; 3]

工作原理：

我们正在遍历列表，在 head 中保留已访问的元素，在 tail 中保留未访问的元素。从 tail 中取出第一个元素，看看它是否等于我们要搜索的 elem。如果找到元素，则反转 head 并附加到 tail 而不删除元素。如果未找到元素，则将 current 附加到 head 并继续。如果我们已到达列表末尾且未找到元素，则 return list 不作任何修改。

示例：

给定的 [1; 2; 3; 4; 5] 列表和元素 3 迭代将如下所示：

head	tail	x	xs
[]	[1; 2; 3; 4; 5]	1	[2; 3; 4; 5]
[1]	[2; 3; 4; 5]	2	[3; 4; 5]
[2; 1]	[3; 4; 5]	3	[4; 5]

最后找到迭代元素，剩下的就是构建列表：[2; 1] 的反向是 [1; 2]，附加到 [4; 5] 并得到 [1; 2; 4; 5]。

注意：head保持反向以提高构建它的性能从O(n2)到O(n)。在第二个分支中将 head 与 xs 组合可以从 O(head.length*2) 改进为 O(head.length) 通过避免将 rev 与 @ 一起使用并手动构建结果列表

Answer 3

您遇到的问题在代码的最后一行

let rec remove l x =
     match l with
     | [] -> []
     | h::t when h = x -> t
     | h::t -> h::(remove l h)
                   ^^^^^^^^^^^

你想保留头部h处理尾部t但是代码没有这样做，参考h和l，而不是 t 和 x.
remove 的类型签名被正确推断为 'a list-> 'a -> 'a list 但在最后一个匹配分支中使用了错误的第二个参数。它使用 h 而不是 x 作为删除参数的元素。
第一个参数也不正确，因为引用 l 在每次递归中都不会改变。需要参考最新的tail t.

所以最后一个匹配分支应该是：

| h::t -> h::(remove t x)

这是更正后的完整代码；

let rec remove l x =
    match l with
    | [] -> []
    | h::t when h = x -> t
    | h::t -> h::(remove t x)

F# 删除列表中第一次出现的元素

F# removing the first occurrence of an element in a list

f#