F:从另一个列表中筛选一个列表中的项目

由于对列表进行了排序,因此可以使用此(非尾部递归)函数在线性时间内解决此问题:

let rec except a b =
    match (a, b) with
    | [], x | x, [] -> x
    | x::xs, y::ys ->
        if x < y then x :: except xs (y::ys)
        elif x > y then y :: except (x::xs) ys
        else except xs ys

尾部递归版本:

let rec except_tail_recursive a b =
    let rec loop acc a b =
        match (a, b) with
        | [], x | x, [] -> (List.rev acc) @ x
        | x::xs, y::ys ->
            if x < y then loop (x::acc) xs (y::ys)
            elif x > y then loop (y::acc) (x::xs) ys
            else loop acc xs ys
    loop [] a b

如果您想要一个纯F解决方案,您的选择将根据您的需求而变化。如果您的列表不包含重复项,并且您不关心输出的顺序,那么您可以这样做:

(Set.of_list a) - (Set.of_list b) |> Set.to_list

如果您知道您的项目是排序的,那么这应该是有效的:

let exclude =
  let rec exclude = function
    | [],_ -> [] 
    | a,[] -> a
    | (x::xs as l),(y::ys as r) -> 
        if x < y then x :: (exclude (xs, r))
        elif x > y then exclude (l, ys)
        else exclude (xs, ys)
  fun a b -> exclude (a,b)

如果您有两个列表,其中可能包含重复项,不必排序,那么您希望结果按照它们出现的顺序排列。 a ,你不关心性能,你可以做:

a |> List.filter (fun x -> not (List.contains x b))

如果您在3.5框架或更高的框架下工作,可以执行以下操作

let c = System.Linq.Enumerable.Except(a,b)

这不是一个纯粹的F解决方案,但它可以完成工作。返回将是 IEnumerable<int> 虽然不是一个F列表。