使用递归和模式匹配从列表中删除元素

Question

在F＃中使用递归，我应该编写一个递归函数来从列表l中删除整数n。该函数接受int和iList并返回一个iList（这是整数列表）

这是我到目前为止：

let rec remove n l
match l with
| E -> failwith "Empty List"
| L(h,E) -> if (h=n) then 0 else h
| L(h,t) -> if (h=n) then remove n t else h + remove n t

在上面的代码中，我设置它，以便它从列表中排除给定的整数n后返回列表中元素的总和而不是列表中的实际元素。

在排除给定的整数n后，我需要帮助返回列表的其余元素。

Answer 1

您可以使用累加器参数（下面的代码中的acc）这样做。 acc参数用于将先前调用的结果携带到递归函数，从而构建最终结果。这是函数式编程中的常见范例。在这种情况下，我们使用空列表启动acc并向其添加元素，但在匹配x时跳过。

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

像这样使用它：

remove 1 [1;2;3] []

另一种方法是使用List.collect：

let remove_use_collect x l =
    let helper y =
        if x = y then [] else [y]
    List.collect helper l

但是我认为理解第一种方法以及如何使用累加器参数很重要，因为它在函数式编程中很常见，在这种情况下你无法修改值。您会发现很多List模块函数都是使用累加器实现的。

Answer 2

sashang的答案假定内置的F＃list类型。由于问题似乎使用了E和L案例的自定义类型，因此这里的答案完全不依赖于List模块或类型。它也不会将累加器暴露为顶级参数，因此调用者无需担心传递初始值：

type ilist = E | L of (int * ilist)

let remove value list =
    let rec remove value acc = function
    | E -> acc
    | L (head, tail) when head = value -> tail |> remove value acc
    | L (head, tail) -> tail |> remove value (L (head, acc))

    list |> remove value E

作为一个重要的注释，这个功能将有效地颠倒列表的顺序。如果需要保留列表的顺序，可以增强功能以​​支持该要求。